用户名: 密码: 验证码:
Maximal-clique partitions and the Roller Coaster Conjecture
详细信息    查看全文
文摘
A graph G is well-covered if every maximal independent set has the same cardinality q  . Let pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si1.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=cb29d56bedf4967c6e1a861773cd8588" title="Click to view the MathML source">ik(G) denote the number of independent sets of cardinality k in G  . Brown, Dilcher, and Nowakowski conjectured that the independence sequence pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si2.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=f9d8bf00eb56754bf6569c4f717c48aa" title="Click to view the MathML source">(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 terms could be in any specified order for some well-covered graph G with independence number q  . Michael and Traves proved the conjecture for pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si4.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=80a6dd70732229dedc901bdb73d10fa9" title="Click to view the MathML source">q<8 and Matchett extended this to pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si5.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=5f69f0d4d20a35081cca8969b997fc8c" title="Click to view the MathML source">q<12.

030">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 pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si204.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=e408a0c7d521ba259c603dd136f8aca0" title="Click to view the MathML source">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 pport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S009731651630053X&_mathId=si68.gif&_user=111111111&_pii=S009731651630053X&_rdoc=1&_issn=00973165&md5=2cbd1adfdffe7cdfbe47356d3c61a4f4" title="Click to view the MathML source">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.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700