### Abstract

A graph G is well-covered if every maximal independent set has the same cardinality q. Let i_{k}(G) denote the number of independent sets of cardinality k in G. Brown, Dilcher, and Nowakowski conjectured that the independence sequence (i_{0}(G),i_{1}(G),…,i_{q}(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 termsi_{⌈q2⌉}(G),i_{⌈q2⌉+1}(G),…,i_{q}(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 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 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.

Original language | English |
---|---|

Pages (from-to) | 25-35 |

Number of pages | 11 |

Journal | Journal of Combinatorial Theory. Series A |

Volume | 145 |

DOIs | |

State | Published - 1 Jan 2017 |

### Fingerprint

### Keywords

- Clique coverings
- Independence polynomial
- Well-covered graphs

### Cite this

*Journal of Combinatorial Theory. Series A*,

*145*, 25-35. https://doi.org/10.1016/j.jcta.2016.06.019