Very well-covered graphs with log-concave independence polynomials

Abstract

If for any $k$ the $k$-th coefficient of a polynomial $I(G;x)$ is equal to the number of stable sets of cardinality $k$ in the graph $G$, then it is called the independence polynomial of $G$ (Gutman and Harary, 1983). Alavi, Malde, Schwenk and Erdos (1987) conjectured that $I(G;x)$ is unimodal, whenever $G$ is a forest, while Brown, Dilcher and Nowakowski (2000) conjectured that $I(G;x)$ is unimodal for any well-covered graph G. Michael and Traves (2003) showed that the assertion is false for well-covered graphs with $a(G)$ > 3 ($a(G)$ is the size of a maximum stable set of the graph $G$), while for very well-covered graphs the conjecture is still open. In this paper we give support to both conjectures by demonstrating that if $a(G)$ < 4, or $G$ belongs to $K_{1,n},P_n:n>0$, then $I(G\ast ;x)$ is log-concave, and, hence, unimodal (where $G\ast$ is the very well-covered graph obtained from $G$ by appending a single pendant edge to each vertex).

8 pages, 4 figures

References in corpus (1)

• A Family of Well-Covered Graphs with Unimodal Independence Polynomials

Cited by in corpus (6)

• On the unimodality of independence polynomials of some graphs
• On the independence polynomial of an antiregular graph
• Operations of graphs and unimodality of independence polynomials
• On f-Symmetries of the Independence Polynomial
• On Symmetry of Independence Polynomials
• The Roller-Coaster Conjecture Revisited