Abstract
A graph G is 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-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),…,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 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
}
Maximal-clique partitions and the Roller Coaster Conjecture. / Cutler, Jonathan; Pebody, Luke.
In: Journal of Combinatorial Theory. Series A, Vol. 145, 01.01.2017, p. 25-35.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - Maximal-clique partitions and the Roller Coaster Conjecture
AU - Cutler, Jonathan
AU - Pebody, Luke
PY - 2017/1/1
Y1 - 2017/1/1
N2 - A graph G is 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-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),…,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 0≤k
AB - A graph G is 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-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),…,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 0≤k
KW - Clique coverings
KW - Independence polynomial
KW - Well-covered graphs
UR - http://www.scopus.com/inward/record.url?scp=84981509997&partnerID=8YFLogxK
U2 - 10.1016/j.jcta.2016.06.019
DO - 10.1016/j.jcta.2016.06.019
M3 - Article
VL - 145
SP - 25
EP - 35
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
SN - 0097-3165
ER -