2014/12/15 by Jonathan Cutler, Cutler, Jonathan, Luke Pebody +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis #math.CO
paper · pdf · doi:10.48550/arxiv.1412.4595
arxiv created 2014/12/15 · arxiv updated 2014/12/16
A graph G is \em well-covered if every maximal independent set has the same cardinality q. Let ik(G) denote the number of independent sets of cardinality k in G. Brown, Dilcher, and Nowakowski conjectured that the independence sequence (i0(G), i1(G), …, iq(G)) was unimodal for any well-ordered graph G with independence number q. Michael and Traves disproved this conjecture. Instead they posited the so-called ``Roller Coaster" Conjecture: that the terms i_\lceil\fracq2\rceil(G), i_\lceil\fracq2\rceil+1(G), …, iq(G) could be in any specified order for some well-covered graph G with independence number q. Michael and Traves proved the conjecture for q<8 and Matchett extended this to q<12. In this paper, we prove the Roller Coaster Conjecture using a construction of graphs with a property related to that of having a maximal-clique partition. In particular, we show, for all pairs of integers 1≤ k<q and positive integers m, that there is a well-covered graph G with independence number q for which every independent set of size k+1 is contained in a unique maximal independent set, but each independent set of size k is contained in at least m distinct independent sets.