کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655024 | 1632927 | 2017 | 11 صفحه PDF | دانلود رایگان |
A graph G is well-covered if every maximal independent set has the same cardinality q . Let ik(G)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))(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<8q<8 and Matchett extended this to q<12q<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
Journal: Journal of Combinatorial Theory, Series A - Volume 145, January 2017, Pages 25–35