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

A graph GG is well-covered   if all its maximal stable sets have the same size, denoted by α(G)α(G) [M.D. Plummer, Some covering concepts in graphs, Journal of Combinatorial Theory 8 (1970) 91–98]. If sksk denotes the number of stable sets of cardinality kk in graph GG, and α(G)α(G) is the size of a maximum stable set, then I(G;x)=∑k=0α(G)skxk is the independence polynomial   of GG [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Mathematica 24 (1983) 97–106]. J.I. Brown, K. Dilcher and R.J. Nowakowski [Roots of independence polynomials of well-covered graphs, Journal of Algebraic Combinatorics 11 (2000) 197–210] conjectured that I(G;x)I(G;x) is unimodal (i.e., there is some j∈{0,1,…,α(G)}j∈{0,1,…,α(G)} such that s0≤⋯≤sj−1≤sj≥sj+1≥⋯≥sα(G)s0≤⋯≤sj−1≤sj≥sj+1≥⋯≥sα(G)) for any well-covered graph GG. T.S. Michael and W.N. Traves [Independence sequences of well-covered graphs: non-unimodality and the roller-coaster conjecture, Graphs and Combinatorics 19 (2003) 403–411] proved that this assertion is true for α(G)≤3α(G)≤3, while for α(G)∈{4,5,6,7}α(G)∈{4,5,6,7} they provided counterexamples.In this paper we show that for any integer α≥8α≥8, there exists a connected well-covered graph GG with α=α(G)α=α(G), whose independence polynomial is not unimodal. In addition, we present a number of sufficient conditions for a graph GG with α(G)≤6α(G)≤6 to have the unimodal independence polynomial.