Abstract
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 Gutman and Trinajstić in 1972. In 2004, Das and Gutman 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 Das and Gutman to the generalized tree, the k-tree, where the results of Das and Gutman are for k=1. Also by showing that maximal outerplanar graphs are 2-trees, we also extend a result of Hou, Li, Song, and Wei who determined sharp upper and lower bounds for M 1 and M 2 values for maximal outerplanar graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Beineke LW, Pippet RE (1969) The number of labeled k-dimensional trees. J Comb Theory 6:200–205
Bollobás B, Erdös P (1998) Graphs of extremal weights. Ars Comb 50:225–233
Chen S, Deng H (2007) Extremal (n,n+1)-graphs with respected to zeroth-order general Randić index. J Math Chem 42:555–564
Das K (2004) Maximizing the sum of the squares of degrees of a graph. Discrete Math 257:57–66
Das K, Gutman I (2004) Some properties of the second Zagreb index. MATCH Commun Math Comput Chem 52:103–112
de Caen D (1998) An upper bound on the sum of squares of degrees in a graph. Discrete Math 185:245–248
Garcia-Domenech R, Galvez J, de Julian-Ortiz JV, Pogliani L (2008) Some new trends in chemical graph theory. Chem Rev 108:1127–1169
Gutman I, Das K (2004) The first Zagreb index 30 years after. MATCH Commun Math Comput Chem 50:83–92
Gutman I, Trinajstić N (1972) Graph theory and molecular orbitals. Total π-electron energy of alternate hydrocarbons. Chem Phys Lett 17:535–538
Hou A, Li S, Song L, Wei B (2011) Sharp bounds for Zagreb indices of maximal outerplanar graphs. J Comb Optim 22:252–269
Li S, Zhou H (2010) On the maximum and minimum Zagreb indices of graphs with connectivity at most k. Appl Math Lett 23:128–132
Lick DR, White AT (1970) k-degenerate subgraphs. Can J Math 22:1082–1096
Song L, Staton W, Wei B (2010) Independence polynomials of k-tree related graphs. Discrete Appl Math 158:943–950
Randić M (1975) On characterization of molecular branching. J Am Chem 97:6609–6615
Xu K (2011) The Zagreb indices of graphs with a given clique number. Appl Math Lett 24(6):1026–1030
Author information
Authors and Affiliations
Corresponding author
Additional information
Partially supported by the Summer Graduate Research Assistantship Program at The University of Mississippi.
Partially supported by College of Liberal Arts Summer Research Grant.
Rights and permissions
About this article
Cite this article
Estes, J., Wei, B. Sharp bounds of the Zagreb indices of k-trees. J Comb Optim 27, 271–291 (2014). https://doi.org/10.1007/s10878-012-9515-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-012-9515-6