A graph
G is
well-covered if every maximal independent set has the same cardinality
q . Let
pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si1.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=cb29d56bedf4967c6e1a861773cd8588" title="Click to view the MathML source">ik(G) denote the number of independent sets of cardinality
k in
G . Brown, Dilcher, and Nowakowski conjectured that the independence sequence
pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si2.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=f9d8bf00eb56754bf6569c4f717c48aa" title="Click to view the MathML source">(i0(G),i1(G),…,iq(G)) was unimodal for any well-covered graph
G with independence number
q. Michael and Traves disproved this conjecture. Instead they posited the so-called “Roller Coaster” Conjecture: that the terms
could be in any specified order for some well-covered graph
G with independence number
q . Michael and Traves proved the conjecture for
pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si4.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=80a6dd70732229dedc901bdb73d10fa9" title="Click to view the MathML source">q<8 and Matchett extended this to
pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si5.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=5f69f0d4d20a35081cca8969b997fc8c" title="Click to view the MathML source">q<12.
030">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 pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si204.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=e408a0c7d521ba259c603dd136f8aca0" title="Click to view the MathML source">0≤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 pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si68.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=2cbd1adfdffe7cdfbe47356d3c61a4f4" title="Click to view the MathML source">k+1 is contained in a unique maximal independent set, but each independent set of size k is contained in at least m distinct maximal independent sets.