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
Loading...
Thumbnail Image
Name

186_2004_Article_317.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

296.61 KB

Format

Adobe PDF

Checksum (MD5)

399d189c71dd9c8f2190fbfad2d95f46

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