Graphs with fixed number of pendent vertices and minimal first Zagreb index

Document Type : Research Paper


1 University of Kragujevac Kragujevac, Serbia

2 Government College University


‎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$‎.


Main Subjects

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