MMN-2382

# On the extremal graphs for Second Zagreb Index with fixed number of vertices and cyclomatic number

**Akbar Ali**, University of Management and Technology, Department of Mathematics, Sialkot, Pakistan,`akbarali.maths@gmail.com`

**Kinkar Ch. Das**, Sungkyunkwan University, Department of Mathematics, Suwon 440- 746, Republic of Korea,`kinkardas2003@googlemail.com`

**Sohail Akhter**, University of Management and Technology, Department of Mathematics, Sialkot, Pakistan,`sohail.akhter@gmail.com`

## Abstract

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