×

zbMATH — the first resource for mathematics

Sharp bounds of the Zagreb indices of \(k\)-trees. (English) Zbl 1318.90070
Summary: For a graph \(G\), the first Zagreb index \(M _{1}\) is equal to the sum of squares of the vertex degrees, and the second Zagreb index \(M _{2}\) is equal to the sum of the products of degrees of pairs of adjacent vertices. The Zagreb indices have been the focus of considerable research in computational chemistry dating back to I. Gutman and N. Trinajstić [“Graph theory and molecular orbitals. Total \(\pi\)-electron energy of alternate hydrocarbons”, Chem. Phys. Lett. 17. 535–538 (1972)]. In 2004, I. Gutman and K. Ch. Das [MATCH Commun. Math. Comput. Chem. 50, 83–92 (2004; Zbl 1053.05115)] determined sharp upper and lower bounds for \(M _{1}\) and \(M _{2}\) values for trees along with the unique trees that obtain the minimum and maximum \(M _{1}\) and \(M _{2}\) values respectively. In this paper, we generalize the results of Gutman and Das [loc. cit.] to the generalized tree, the \(k\)-tree, where the results of Gutman and Das [loc. cit.] are for \(k=1\). Also by showing that maximal outerplanar graphs are 2-trees, we also extend a result of A. Hou et al. [J. Comb. Optim. 22, No. 2, 252–269 (2011; Zbl 1250.90102)] who determined sharp upper and lower bounds for \(M _{1}\) and \(M _{2}\) values for maximal outerplanar graphs.

MSC:
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beineke, LW; Pippet, RE, The number of labeled k-dimensional trees, J Comb Theory, 6, 200-205, (1969) · Zbl 0175.20904
[2] Bollobás, B; Erdös, P, Graphs of extremal weights, Ars Comb, 50, 225-233, (1998) · Zbl 0963.05068
[3] Chen, S; Deng, H, Extremal (\(n\),\(n\)+1)-graphs with respected to zeroth-order general randić index, J Math Chem, 42, 555-564, (2007) · Zbl 1127.92048
[4] Das, K, Maximizing the sum of the squares of degrees of a graph, Discrete Math, 257, 57-66, (2004) · Zbl 1051.05033
[5] Das, K; Gutman, I, Some properties of the second Zagreb index, MATCH Commun Math Comput Chem, 52, 103-112, (2004) · Zbl 1077.05094
[6] Caen, D, An upper bound on the sum of squares of degrees in a graph, Discrete Math, 185, 245-248, (1998) · Zbl 0955.05059
[7] Garcia-Domenech, R; Galvez, J; Julian-Ortiz, JV; Pogliani, L, Some new trends in chemical graph theory, Chem Rev, 108, 1127-1169, (2008)
[8] Gutman, I; Das, K, The first Zagreb index 30 years after, MATCH Commun Math Comput Chem, 50, 83-92, (2004) · Zbl 1053.05115
[9] Gutman, I; Trinajstić, N, Graph theory and molecular orbitals. total \(π\)-electron energy of alternate hydrocarbons, Chem Phys Lett, 17, 535-538, (1972)
[10] Hou, A; Li, S; Song, L; Wei, B, Sharp bounds for Zagreb indices of maximal outerplanar graphs, J Comb Optim, 22, 252-269, (2011) · Zbl 1250.90102
[11] Li, S; Zhou, H, On the maximum and minimum Zagreb indices of graphs with connectivity at most \(k\), Appl Math Lett, 23, 128-132, (2010) · Zbl 1201.05028
[12] Lick, DR; White, AT, K-degenerate subgraphs, Can J Math, 22, 1082-1096, (1970) · Zbl 0202.23502
[13] Song, L; Staton, W; Wei, B, Independence polynomials of \(k\)-tree related graphs, Discrete Appl Math, 158, 943-950, (2010) · Zbl 1219.05133
[14] Randić, M, On characterization of molecular branching, J Am Chem, 97, 6609-6615, (1975) · Zbl 0770.60091
[15] Xu, K, The Zagreb indices of graphs with a given clique number, Appl Math Lett, 24, 1026-1030, (2011) · Zbl 1216.05041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.