The independent set sequence of some families of trees

Abstract

For a tree $T$, let $i_T(t)$ be the number of independent sets of size $t$ in $T$. It is an open question, raised by Alavi, Malde, Schwenk and Erdős, whether the sequence $(i_T(t){)}_{t\ge 0}$ is always unimodal. Here we answer the question in the affirmative for some recursively defined families of trees, specifically paths with auxiliary trees dropped from the vertices in a periodic manner. In particular, extending a result of Wang and B.-X. Zhu, we show unimodality of the independent set sequence of a path on $2n$ vertices with ${\ell }_1$ and ${\ell }_2$ pendant edges dropped alternately from the vertices of the path, ${\ell }_1,{\ell }_2$ arbitrary. We also show that the independent set sequence of any tree becomes unimodal if sufficiently many pendant edges are dropped from any single vertex, or if $k$ pendant edges are dropped from every vertex, for sufficiently large $k$. This in particular implies the unimodality of the independent set sequence of some non-periodic caterpillars.

Some minor corrections. To appear in Australas. J. Combin volume 70 issue 2 (2018)

References in corpus (3)

• On the unimodality of independence polynomials of some graphs
• On trees with real rooted independence polynomial
• On Unimodality of Independence Polynomials of some Well-Covered Trees

Cited by in corpus (4)

• On trees with real rooted independence polynomial
• Independent Sets of Random Trees and of Sparse Random Graphs
• Lorentzian polynomials and the independence sequences of graphs
• $PC$-polynomial of graph