Independence polynomials of well-covered graphs: generic counterexamples for the unimodality conjecture

Original · EN

A graph G is well-covered if all its maximal stable sets have the same size, denoted by alpha(G) (M. D. Plummer, 1970). 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 graph G, then it is called the independence polynomial of G (Gutman and Harary, 1983). J. I. Brown, K. Dilcher and R. J. Nowakowski (2000) conjectured that I(G;x) is unimodal (that is, there exists an index k such that the part of the sequence of coefficients from the first to k-th is non-decreasing while the other part of coefficients is non-increasing) for any well-covered graph G. T. S. Michael and W. N. Traves (2002) proved that this assertion is true for alpha(G) < 4, while for alpha(G) from the set 4,5,6,7 they provided counterexamples. In this paper we show that for any integer alpha > 7, there exists a (dis)connected well-covered graph G with alpha = alpha(G), whose independence polynomial is not unimodal. In addition, we present a number of sufficient conditions for a graph G with alpha(G) < 7 to have unimodal independence polynomial.