The stable set polytope of icosahedral graphs

详细信息    查看全文

• 作者：Anna Galluccio ^{galluccio@iasi.cnr.it" class="auth_mail" title="E-mail the corresponding author} ; Claudio Gentile ^{gentile@iasi.cnr.it" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Stable set polytope ; Claw-free graphs ; Icosahedron
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：614-625
• 全文大小：485 K

文摘

The problem of finding a complete linear description of the stable set polytope of claw-free graphs has been a major topic in combinatorial optimization in the last decades and it is still not completely solved. While it is known that this linear description contains facet defining inequalities with arbitrarily many and arbitrarily high coefficients, the set of claw-free graphs whose stable set polytope is described only by inequalities with lsi3" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003490&_mathId=si3.gif&_user=111111111&_pii=S0012365X15003490&_rdoc=1&_issn=0012365X&md5=83f1084b0c88c6faba6beb6bf04794f1" title="Click to view the MathML source">{0,1,2}lass="mathContainer hidden">lass="mathCode">low="scroll">{0,1,2}-valued coefficients is considerably large. In fact Galluccio et al. (2014) proved that this set contains almost all claw-free graphs with stability number greater than three plus some of the building blocks with stability number smaller than or equal to three, identified by Chudnovsky and Seymour in their Structure Theorem.

Here we show that another important class of claw-free graphs with stability number three belongs to this set: the class of icosahedral graphs, named lsi4" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003490&_mathId=si4.gif&_user=111111111&_pii=S0012365X15003490&_rdoc=1&_issn=0012365X&md5=3fbec9a3ca6e828c8eace8a1bf3c4b77" title="Click to view the MathML source">S₁lass="mathContainer hidden">lass="mathCode">low="scroll">S1 by Chudnovsky and Seymour (2008). In particular, we prove that the stable set polytope of icosahedral graphs is described by: rank, lifted 5-wheel and lifted wedge inequalities, and all these linear inequalities have coefficients in lsi3" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X15003490&_mathId=si3.gif&_user=111111111&_pii=S0012365X15003490&_rdoc=1&_issn=0012365X&md5=83f1084b0c88c6faba6beb6bf04794f1" title="Click to view the MathML source">{0,1,2}lass="mathContainer hidden">lass="mathCode">low="scroll">{0,1,2}.