Maximal-clique partitions and the Roller Coaster Conjecture

Jonathan Cutler, Luke Pebody

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)25-35
Number of pages11
JournalJournal of Combinatorial Theory. Series A
Volume145
DOIs
StatePublished - 1 Jan 2017

Fingerprint

Maximal Clique
Maximal Independent Set
Partition
Independence number
Independent Set
Graph in graph theory
Cardinality
Integer
Denote
Distinct

Keywords

  • Clique coverings
  • Independence polynomial
  • Well-covered graphs

Cite this

@article{a7467f6ef03a4717ace814f15e53f314,
title = "Maximal-clique partitions and the Roller Coaster Conjecture",
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",
keywords = "Clique coverings, Independence polynomial, Well-covered graphs",
author = "Jonathan Cutler and Luke Pebody",
year = "2017",
month = "1",
day = "1",
doi = "10.1016/j.jcta.2016.06.019",
language = "English",
volume = "145",
pages = "25--35",
journal = "Journal of Combinatorial Theory. Series A",
issn = "0097-3165",
publisher = "Academic Press Inc.",

}

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 journalArticle

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

AN - SCOPUS:84981509997

VL - 145

SP - 25

EP - 35

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

SN - 0097-3165

ER -