Maximal-clique partitions and the Roller Coaster Conjecture

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:145

Article

Cutler, Jonathan¹  Pebody, Luke² 

[1] Montclair State Univ, Dept Math Sci, Montclair, NJ 07043 USA

[2] Rokos Capital Management LLP, 23 Savile Row, London W1S 2ET, England

关键词: Independence polynomial;    Well-covered graphs;    Clique coverings;   

DOI  :  10.1016/j.jcta.2016.06.019

来源: Elsevier

【 摘 要 】

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(o)(G),i(1)(G),...,i(q)(G)) was unirnodal 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 i (inverted right perpendicular q/2 inverted left perpendicular) (G), i (inverted right perpendicular q/2 inverted left perpendicular) + 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. (C) 2016 Elsevier Inc. All rights reserved.

【 授权许可】

Free