The first Zagreb index $M_1$ of a graph $G$ is equal to the sum of squares of degrees of the vertices of $G$. Goubko proved that for trees with $n_1$ pendent vertices, $M_1 \geq 9\,n_1-16$. We show how this result can be extended to hold for any connected graph with cyclomatic number $\gamma \geq 0$. In addition, graphs with $n$ vertices, $n_1$ pendent vertices, cyclomatic number $\gamma$, and minimal $M_1$ are characterized. Explicit expressions for minimal $M_1$ are given for $\gamma=0,1,2$, which directly can be extended for $\gamma>2$.
S. Chen and W. Liu (2014). Extremal Zagreb indices of graphs with a given number of cut edges. Graphs Combin.. 30, 109-118 H. Deng (2007). A unified approach to the extremal Zagreb indices of trees, unicyclic graphs and bicyclic graphs. MATCH Commun. Math. Comput. Chem.. 57, 597-616 B. Furtula, I. Gutman and M. Dehmer (2013). On structure--sensitivity of degree--based topological indices. Appl. Math. Comput.. 219, 8973-8978 M. Goubko (2014). Minimizing degree--based topological indices for trees with given number of pendent vertices. MATCH Commun. Math. Comput. Chem.. 71, 33-46 M. Goubko and I. Gutman (2014). Degree--based topological indices: Optimal trees with given number of pendents. Appl. Math. Comput.. 240, 387-398 M. Goubko and T. R\'eti (2014). Note on minimizing degree--based topological indices of trees with given number of pendent vertices. MATCH Commun. Math. Comput. Chem.. 72, 633-639 I. Gutman (2013). Degree--based topological indices. Croat. Chem. Acta. 86, 351-361 I. Gutman and M. Goubko (2013). Trees with fixed number of pendent vertices with minimal first Zagreb index. Bull. Int. Math. Virtual Inst.. 3, 161-164 I. Gutman and N. Trinajsti\'c (1972). Graph theory and molecular orbitals. Total $\pi$-electron energy of alternant hydrocarbons. Chem. Phys. Lett.. 17, 535-538 I. Gutman and K. C. Das (2004). The first Zagreb index 30 years after. MATCH Commun. Math. Comput. Chem.. (50), 83-92 R. Kazemi (2013). Probabilistic analysis
of the first Zagreb index. Trans. Comb.. 2 (2), 35-40 S. Li, H. Yang and Q. Zhao (2012). Sharp bounds on Zagreb indices of cacti with $k$ pendent vertices. Filomat. 26, 1189-1200 K. Xu, K. C. Das and S. Balachandran (2014). Maximizing the Zagreb indices of $(n,m)$-graphs. MATCH Commun. Math. Comput. Chem.. 72, 641-654 Q. Zhao and S. Li (2010). Sharp bounds for the Zagreb indices of bicyclic graphs with $k$-pendent vertices. Discrete Appl. Math.. 158, 1953-1962
Gutman, I., Jamil, M., & Akhter, N. (2015). Graphs with fixed number of pendent vertices and minimal first Zagreb index. Transactions on Combinatorics, 4(1), 43-48. doi: 10.22108/toc.2015.6029
MLA
Ivan Gutman; Muhammad Kamran Jamil; Naveed Akhter. "Graphs with fixed number of pendent vertices and minimal first Zagreb index". Transactions on Combinatorics, 4, 1, 2015, 43-48. doi: 10.22108/toc.2015.6029
HARVARD
Gutman, I., Jamil, M., Akhter, N. (2015). 'Graphs with fixed number of pendent vertices and minimal first Zagreb index', Transactions on Combinatorics, 4(1), pp. 43-48. doi: 10.22108/toc.2015.6029
VANCOUVER
Gutman, I., Jamil, M., Akhter, N. Graphs with fixed number of pendent vertices and minimal first Zagreb index. Transactions on Combinatorics, 2015; 4(1): 43-48. doi: 10.22108/toc.2015.6029
)
