Maximal-clique partitions and the Roller Coaster Conjecture
Maximal-clique partitions and the Roller Coaster Conjecture
复制标题
DOI：
10.1016/j.jcta.2016.06.019
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Jonathan Cutler;Luke Pebody
中科院分区：
文献类型：
--
作者：
Jonathan Cutler;Luke Pebody
一个图G是良好覆盖的，如果每个极大独立集具有相同的基数q。设ik（G）表示G中基数为k的独立集的个数. Brown，Dilcher和Nowakowski证明了对于任意具有独立数q的覆盖良好的图G，独立序列（i 0（G），i1（G），.，iq（G））是单峰的.迈克尔和特拉维斯推翻了这个猜想。相反，他们提出了所谓的“过山车”猜想：对于具有独立数q的覆盖良好的图G，项i <$q 2 <$（G），i <$q 2 <$+ 1（G），.，i q（G）可以是任意指定的顺序。Michael和Traves证明了q< 8的猜想，Matchett将其扩展到q< 12。在本文中，我们证明了过山车猜想使用的一个结构图的性质有关，有一个最大团划分。特别地，我们证明了，对于所有的整数对0≤ k< q和正整数m，存在一个独立数为q的完全覆盖图G，使得每个大小为k+ 1的独立集包含在唯一的极大独立集中，但每个大小为k的独立集包含在至少m个不同的极大独立集中.
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 terms i⌈ q 2⌉(G), i⌈ q 2⌉+ 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.