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

**Download 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

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

- Ahmadi, M. B., & Alimorad Dastkhezr, H. (2014) An algorithm for computing the Merrifield–Simmons index, MATCH Commun. Math. Comput. Chem., 71, 355–359.
- 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.
- Bousquet-Melou, M., Linusson, S., & Nevo, E. (2008) On the independence complex of square grids, Journal of Algebraic Combinatorics, 27, 423–450.
- Brown, J. I., Dilcher, K., & Nowakowski, R. J. (2000) Roots of independence polynomials of well-covered graphs, Journal of Algebraic Combinatorics, 11, 197–210.
- 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.
- 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.
- Gutman, I. (1991) Topological properties of benzenoid systems. Merrifield–Simmons indices and independence polynomials of unbranched catafusenes, Rev. Roum. Chim., 36, 379–388.
- Gutman, I., & Harary, F. (1983) Generalizations of the matching polynomial, Utilitas Mathematica, 24, 97–106.
- Hamidoune, Y. O. (1990) On the number of independent k-sets in a claw-free graph, Journal of Combinatorial Theory B, 50, 241–244.
- Hoede, C., & Li, X. (1994) Clique polynomials and independent set polynomials of graphs, Discrete Mathematics, 125, 219–228.
- Keilson, J., & Gerber, H. (1971) Some results for discrete unimodality, Journal of the American Statistical Association, 334, 386–389.
- Levit, V. E., & Mandrescu, E. (2002) On well-covered trees with unimodal independence polynomials, Congressus Numerantium, 159, 193–202.
- 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.
- Levit, V. E., & Mandrescu, E. (2003) A family of well-covered graphs with unimodal independence polynomials, Congressus Numerantium, 165, 195–207.
- Levit, V. E., & Mandrescu, E. (2004) Very well-covered graphs with log-concave independence polynomials, Carpathian Journal of Mathematics, 20, 73–80.
- 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.
- 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.
- 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.
- Li, X., Zhao, H., & Gutman, I. (2005) On the Merrifield–Simmons index of trees, MATCH Commun. Math. Comput. Chem., 54, 389–402.
- Merrifield, R. E., & Simmons, H. E. (1989) Topological methods in chemistry, New York, John Wiley and Sons.
- Moon, J. W., & Moser, L. (1965) On cliques in graphs, Israel Journal of Mathematics, 3, 23–28.
- Plummer, M. D. (1970) Some covering concepts in graphs, Journal of Combinatorial Theory, 8, 91–98.
- Prodinger, H., & Tichy, R. F. (1982) Fibonacci numbers of graphs, Fibonacci Quarterly, 20, 16–21.
- Sagan, B. (1988) A note on independent sets in trees, SIAM Journal of Discrete Mathematics, 1, 105–108.
- 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.
- Wilf, H. (1986) The number of maximal independent sets in a tree, SIAM Journal of Algebraic Discrete Methods, 7, 125–130.
- Zykov, A. A. (1990) Fundamentals of graph theory, BCS Associates, Moscow.

## Related papers

## Cite this paper

Mandrescu, E., & Spivak, A. (2016). Maximal trees with log-concave independence polynomials. Notes on Number Theory and Discrete Mathematics, 22(2), 44-53.