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. Journal articles
  4. On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs
 
research article

On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs

Liebling, Thomas M.  
•
Oriolo, Gianpaolo
•
Spille, Bianca  
Show more
2004
Mathematical Methods of Operations Research

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Giles 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 coefficients (rank facets have only 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 observed by Cook [3] and Shepherd [18].

  • Files
  • Details
  • Metrics
Type
research article
DOI
10.1007/s001860300317
Web of Science ID

WOS:000188748200002

Author(s)
Liebling, Thomas M.  
Oriolo, Gianpaolo
Spille, Bianca  
Stauffer, Gautier  
Date Issued

2004

Publisher

Springer-Verlag

Published in
Mathematical Methods of Operations Research
Volume

59

Issue

1

Start page

25

End page

35

Subjects

Stable sets

•

Claw-free graphs

•

Quasi-line graphs

•

Circulant graphs

•

Clique family inequalities

Note

PRO 04.07.03

National Licences

Editorial or Peer reviewed

REVIEWED

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/223107
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