Maximal trees with log-concave independence polynomials

Eugen Mandrescu and Alexander Spivak
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 22, 2016, Number 2, Pages 44–53
Full paper (PDF, 182 Kb)

Details

Authors and affiliations

Eugen Mandrescu
Department of Computer Sciences, Holon Institute of Technology
52 Golomb Str., Holon 5810201, Israel

Alexander Spivak
Department of Computer Sciences, Holon Institute of Technology
52 Golomb Str., Holon 5810201, Israel

Abstract

If s_k denotes the number of independent sets of cardinality k in graph G, and α(G) is the size of a maximum independent set, then

   

is the independence polynomial of G (I. Gutman and F. Harary, 1983, [8]). The Merrifield–Simmons index σ(G) (known also as the Fibonacci number) of a graph G is defined as the number of all independent sets of G. Y. Alavi, P. J. Malde, A. J. Schwenk and P. Erdos (1987, [2]) conjectured that I(T,x) is unimodal whenever T is a tree, while, in general, they proved that for each permutation π of {1, 2, …, α} there is a graph G with α(G) = α such that s_π(1) < s_π(2) < … < s_π(α). By maximal tree on n vertices we mean a tree having a maximum number of maximal independent sets among all the trees of order n. B. Sagan proved that there are three types of maximal trees, which he called batons [24].

In this paper we derive closed formulas for the independence polynomials and Merrifield–Simmons indices of all the batons. In addition, we prove that I(T,x) is log-concave for every maximal tree T having an odd number of vertices. Our findings give support to the above mentioned conjecture.

Keywords

• Independent set
• Independence polynomial
• Log-concave sequence
• Tree

AMS Classification

• 05C05
• 05C69
• 05C31

References

1. Ahmadi, M. B., & Alimorad Dastkhezr, H. (2014) An algorithm for computing the Merrifield–Simmons index, MATCH Commun. Math. Comput. Chem., 71, 355–359.
2. Alavi, Y. P., Malde, J., Schwenk, A. J., & Erd¨os, P. (1987) The vertex independence sequence of a graph is not constrained, Congressus Numerantium, 58, 15–23.
3. Bousquet-Melou, M., Linusson, S., & Nevo, E. (2008) On the independence complex of square grids, Journal of Algebraic Combinatorics, 27, 423–450.
4. Brown, J. I., Dilcher, K., & Nowakowski, R. J. (2000) Roots of independence polynomials of well-covered graphs, Journal of Algebraic Combinatorics, 11, 197–210.
5. Engstr¨om, A. (2009) Upper bounds on the Witten index for supersymmetric lattice models by discrete Morse theor,European Journal of Combinatorics, 30, 429–438.
6. Gutman, I. (1990) Fragmentation formulas for the number of Kekule structures, Hosoya and Merrifield–Simmons indices and related graph invariants, Coll. Sci. Pap. Fac. Sci. Kragujevac, 11, 11–18.
7. Gutman, I. (1991) Topological properties of benzenoid systems. Merrifield–Simmons indices and independence polynomials of unbranched catafusenes, Rev. Roum. Chim., 36, 379–388.
8. Gutman, I., & Harary, F. (1983) Generalizations of the matching polynomial, Utilitas Mathematica, 24, 97–106.
9. Hamidoune, Y. O. (1990) On the number of independent k-sets in a claw-free graph, Journal of Combinatorial Theory B, 50, 241–244.
10. Hoede, C., & Li, X. (1994) Clique polynomials and independent set polynomials of graphs, Discrete Mathematics, 125, 219–228.
11. Keilson, J., & Gerber, H. (1971) Some results for discrete unimodality, Journal of the American Statistical Association, 334, 386–389.
12. Levit, V. E., & Mandrescu, E. (2002) On well-covered trees with unimodal independence polynomials, Congressus Numerantium, 159, 193–202.
13. Levit, V. E., & Mandrescu, E. (2003) On unimodality of independence polynomials of some well-covered trees, in: C. S. Calude (Eds.), DMTCS LNCS, 2731, Springer-Verlag, 237– 256.
14. Levit, V. E., & Mandrescu, E. (2003) A family of well-covered graphs with unimodal independence polynomials, Congressus Numerantium, 165, 195–207.
15. Levit, V. E., & Mandrescu, E. (2004) Very well-covered graphs with log-concave independence polynomials, Carpathian Journal of Mathematics, 20, 73–80.
16. Levit, V. E., & Mandrescu, E. (2005) The independence polynomial of a graph – a survey, Proceedings of the First International Conference on Algebraic Informatics, Aristotle University of Thessaloniki, Greece, 233–254.
17. Levit, V. E., & Mandrescu, E. (2006) Independence polynomials of well-covered graphs: Generic counterexamples for the unimodality conjecture, European Journal of Combinatorics, 27, 931–939.
18. Levit, V. E., & Mandrescu, E. (2011) A simple proof of an inequality connecting the alternating number of independent sets and the decycling number, Discrete Mathematics, 311, 1204–1206.
19. Li, X., Zhao, H., & Gutman, I. (2005) On the Merrifield–Simmons index of trees, MATCH Commun. Math. Comput. Chem., 54, 389–402.
20. Merrifield, R. E., & Simmons, H. E. (1989) Topological methods in chemistry, New York, John Wiley and Sons.
21. Moon, J. W., & Moser, L. (1965) On cliques in graphs, Israel Journal of Mathematics, 3, 23–28.
22. Plummer, M. D. (1970) Some covering concepts in graphs, Journal of Combinatorial Theory, 8, 91–98.
23. Prodinger, H., & Tichy, R. F. (1982) Fibonacci numbers of graphs, Fibonacci Quarterly, 20, 16–21.
24. Sagan, B. (1988) A note on independent sets in trees, SIAM Journal of Discrete Mathematics, 1, 105–108.
25. Yu, A., & Tian, F. (2006) A kind of graphs with minimal Hosoya indices and maximal Merrifield–Simmons indices, MATCH Commun. Math. Comput. Chem., 55, 103–118.
26. Wilf, H. (1986) The number of maximal independent sets in a tree, SIAM Journal of Algebraic Discrete Methods, 7, 125–130.
27. Zykov, A. A. (1990) Fundamentals of graph theory, BCS Associates, Moscow.