2004/06/30 by Vadim E. Levit, Levit, Vadim E., Eugen Mandrescu +1
Mathematics · #05C17 (Primary) 05A20 #05C69 #11B83 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A20 #msc:05C17 #msc:05C69 #msc:11B83
paper · pdf · doi:10.48550/arxiv.math/0406623
10 pages, 4 figures
arxiv created 2004/06/30 · arxiv updated 2009/12/01
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). Let a be the size of a maximum stable set. Alavi, Malde, Schwenk and Erdos (1987)conjectured that I(T,x) is unimodal for any tree T, while, in general, they proved that for any permutation p of 1,2,...,a there is a graph such that sp(1)<sp(2)<...<sp(a). Brown, Dilcher and Nowakowski (2000) conjectured that I(G;x) is unimodal for any well-covered graph. Michael and Traves (2002) provided examples of well-covered graphs with non-unimodal independence polynomials. They proposed the "roller-coaster" conjecture: for a well-covered graph, the subsequence (sa/2,sa/2+1,...,sa) is unconstrained in the sense of Alavi et al. The conjecture of Brown et al. is still open for very well-covered graphs. In this paper we prove that s(2a-1)/3>=...>=sa-1>=sa are valid for any (a) bipartite graph G; (b) quasi-regularizable graph G on 2a vertices. In particular, we infer that this is true for (a) trees, thus doing a step in an attempt to prove Alavi et al.' conjecture; (b) very well-covered graphs. Consequently, for this case, the unconstrained subsequence appearing in the roller-coaster conjecture can be shorten to (sa/2,sa/2+1,...,s(2a-1)/3). We also show that the independence polynomial of a very well-covered graph G is unimodal for a<10, and is log-concave whenever a<6.