MMN-2382

The cyclomatic number of a graph $G$ (is denoted by $\nu$) is the minimum number of edges of $G$ whose removal makes $G$ as acyclic. Denote by $\mathbb{G}_{n,\nu}$ the collection of all $n$-vertex connected graphs with cyclomatic number $\nu$. The elements of $\mathbb{G}_{n,\nu}$ with maximum second Zagreb ($M_2$) index (for $\nu\le4$ and $\nu=\frac{k(k-3)}{2}+1$, where $4\le k\le n-2$) and with minimum $M_2$ index (for $\nu\le2$) have already been reported in the literature. The main contribution of the present article is the characterization of graphs in the collection $\mathbb{G}_{n,\nu}$ with minimum $M_2$ index for $\nu\ge 3$ and $n\ge 2(\nu-1)$. The obtained extremal graphs, are molecular graphs and thereby, also minimize $M_2$ index among all the connected molecular $n$-vertex graphs with cyclomatic number $\nu\ge3$, where $n\ge2(\nu-1)$. For $n\ge 6$, the graph having maximum $M_2$ value in the collection $\mathbb{G}_{n,5}$ has also been characterized and thereby a conjecture posed by Xu \textit{et al.} [\textit{MATCH Commun. Math. Comput. Chem.} \textbf{72} (2014) 641--654] is confirmed for $\nu=5$.

Vol. 23 (2022), No. 1, pp. 41-50

DOI: 10.18514/MMN.2022.2382

Download: MMN-2382