Maximal-clique partitions and the Roller Coaster Conjecture

详细信息    查看全文

• 作者：Jonathan Cutler^a ; ¹ ; ^{jonathan.cutler@montclair.edu" class="auth_mail" title="E-mail the corresponding author} ; Luke Pebody^b ; ^{luke@pebody.org" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Independence polynomial ; Well-covered graphs ; Clique coverings
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：145
• 期：Complete
• 页码：25-35
• 全文大小：313 K

文摘

A graph G is well-covered if every maximal independent set has the same cardinality q  . Let 651630053X&_mathId=si1.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=cb29d56bedf4967c6e1a861773cd8588" title="Click to view the MathML source">i_k(G)$i_k(G)$ denote the number of independent sets of cardinality k in G  . Brown, Dilcher, and Nowakowski conjectured that the independence sequence 651630053X&_mathId=si2.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=f9d8bf00eb56754bf6569c4f717c48aa" title="Click to view the MathML source">(i₀(G),i₁(G),…,i_q(G))$(i_0(G),i_1(G),\dots ,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 could be in any specified order for some well-covered graph G with independence number q  . Michael and Traves proved the conjecture for 651630053X&_mathId=si4.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=80a6dd70732229dedc901bdb73d10fa9" title="Click to view the MathML source">q<8$q<8$ and Matchett extended this to 651630053X&_mathId=si5.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=5f69f0d4d20a35081cca8969b997fc8c" title="Click to view the MathML source">q<12$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 651630053X&_mathId=si204.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=e408a0c7d521ba259c603dd136f8aca0" title="Click to view the MathML source">0≤k<q$0\le 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 651630053X&_mathId=si68.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=2cbd1adfdffe7cdfbe47356d3c61a4f4" title="Click to view the MathML source">k+1$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.