Abstract
An independent set of a graph G is a set of pairwise non-adjacent vertices. Let \(i_k = i_k(G)\) be the number of independent sets of cardinality k of G. The independence polynomial \(I(G, x)=\sum _{k\geqslant 0}i_k(G)x^k\) defined first by Gutman and Harary has been the focus of considerable research recently, whereas \(i(G)=I(G, 1)\) is called the Merrifield–Simmons index of G. In this paper, we first proved that among all trees of order n, the kth coefficient \(i_k\) is smallest when the tree is a path, and is largest for star. Moreover, the graph among all trees of order n with diameter at least d whose all coefficients of I(G, x) are largest is identified. Then we identify the graphs among the n-vertex unicyclic graphs (resp. n-vertex connected graphs with clique number \(\omega \)) which simultaneously minimize all coefficients of I(G, x), whereas the opposite problems of simultaneously maximizing all coefficients of I(G, x) among these two classes of graphs are also solved respectively. At last we characterize the graph among all the n-vertex connected graph with chromatic number \(\chi \) (resp. vertex connectivity \(\kappa \)) which simultaneously minimize all coefficients of I(G, x). Our results may deduce some known results on Merrifield–Simmons index of graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy JA, Murty USR (2008) Graph theory. Graduate texts in mathematics, vol 244. Springer, New York
Brown JI, Dilcher K, Karl M, Dante V (2013) On the roots of expected independence polynomials. J Graph Theory 73(3):322–326
Chudnovsky M, Seymour P (2007) The roots of the independence polynomial of a claw-free graphs. J Comb Theory Ser B 97:350–357
Gutman I, Harary F (1983) Generalizations of the matching polynomial. Utilitas Math 24:97–106
Gutman I, Radenković S, Li N, Li SC (2008) Extremal energy trees. MATCH Commun Math Comput Chem 59(2):315–320
Hoede C, Li X (1994) Clique polynomials and independant set polynomials of graphs. Discrete Math 125:219–228
Hopkins G, Staton W (1984) Some identities arising from the Fibonacci numbers of certain graphs. Fibonacci Quart 22:255–258
Levit VE, Mandrescu E (2006) Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture. Eur J Comb 27(6):931–939
Li SC, Li XC (2009) On tricyclic graphs of a given diamater with minimal energy. Linear Algebra Appl 430(1):370–385
Li SC, Wang SJ (2012) Further analysis on the total number of subtrees of trees. Electron J Comb 19(4):14
Li SL, Yan WG (2014) The matching energy of graphs with given parameters. Discrete Appl Math 162:415–420
Li X, Li Z, Wang L (2003) The inverse problems for some topological indices in combinatorial chemistry. J Comput Biol 10:47–55
Li SC, Li XC, Wei J (2009) On the extremal Merrifield–Simmons index and Hosoya index of quasi-tree graphs. Discrete Appl Math 157(13):2877–2885
Merrifield RE, Simmons HE (1989) Topological methods in chemistry. Wiley, New York
Prodinger H, Tichy RF (1982) Fibonacci numbers of graphs. Fibonacci Quart 20:16–21
Ren HZ, Zhang FJ (2007) Extremal double hexagonal chains with respect to \(k\)-matchings and \(k\)-independant sets. Discrete Appl Math 155:2269–2281
Song LZ, Staton W, Wei B (2010) Independence polynomials of \(k\)-tree related graphs. Discrete Appl Math 158(8):943–950
Székely LA, Wang H (2005) On subtrees of trees. Adv Appl Math 34:138–155
Wagner S, Gutman I (2010) Maxima and minima of the Hosoya index and the Merrifield–Simmons index: a survey of results and techniques. Acta Appl Math 112(3):323–346
Wang Y, Zhu BX (2011) On the unimodality of independence polynomials of some graphs. Eur J Comb 32(1):10–20
Xu KX (2010) On the Hosoya index and the Merrifield–Simmons index of graphs with a given clique number. Appl Math Lett 23:395–398
Zeng YQ, Zhang FJ (2007) Extremal polyomino chains on \(k\)-matchings and \(k\)-independant sets. J Math Chem 42(2):125–140
Zhang LZ, Zhang FJ (2000) Extremal hexagonal chains concerning \(k\)-matchings and \(k\)-independant sets. J Math Chem 27:319–329
Zhu ZX, Yuan C, Andriantiana EOD, Wagner S (2014) Graphs with maximal Hosoya index and minimal Merrifield–Simmons index. Discrete Math 329:77–87
Author information
Authors and Affiliations
Corresponding author
Additional information
Financially supported by the National Natural Science Foundation of China (Grant No. 11271149), the Program for New Century Excellent Talents in University (Grant No. NCET-13-0817) and the Special Fund for Basic Scientific Research of Central Colleges (Grant No. CCNU15A02052).
Rights and permissions
About this article
Cite this article
Li, S., Liu, L. & Wu, Y. On the coefficients of the independence polynomial of graphs. J Comb Optim 33, 1324–1342 (2017). https://doi.org/10.1007/s10878-016-0037-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-016-0037-5