Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. on Non-Rank Facets of the Stable Set Polytope of Claw-Free Graphs and Circulant Graphs
 
report

on Non-Rank Facets of the Stable Set Polytope of Claw-Free Graphs and Circulant Graphs

Liebling, T.  
•
Oriolo, G.
•
Spille, B.  
Show more
2003

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Gilles and Trotter (7) by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequality with (a,a+1) valued coefficinets (rank facets have onnly coefficients 0, 1), and (ii) providing new facets of the stable set polytope with up to five different non-zero coefficients for claw-free graphs. We prove that coefficients have to be consecutive in any facet with exactly two different non-zero coefficients (assuming they are relatively prime). Last but not least, we present a complete description of the stable set polytope for graphs with stability number 2, already obseerved by Cook (3) and Shepperd (18)

  • Details
  • Metrics
Type
report
Author(s)
Liebling, T.  
Oriolo, G.
Spille, B.  
Stauffer, G.  
Date Issued

2003

Note

RO 2003 0512

Written at

EPFL

EPFL units
ROSO  
Available on Infoscience
February 13, 2006
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/223052
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés