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. A Magnetic Procedure for the Stability Number
 
research article

A Magnetic Procedure for the Stability Number

Hertz, Alain
•
de Werra, Dominique  
2009
Graphs And Combinatorics

A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new vertex linked to all common neighbours of u and v without changing the stability number. We prove that all graphs containing no chordless cycle C-k (k >= 5) and none of eleven forbidden subgraphs can be reduced to a stable set by repeated use of magnets. For such graphs a polynomial algorithm is given to determine the stability number.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s00373-010-0886-0
Web of Science ID

WOS:000274852300005

Author(s)
Hertz, Alain
de Werra, Dominique  
Date Issued

2009

Published in
Graphs And Combinatorics
Volume

25

Start page

707

End page

716

Subjects

Stable set

•

Magnet

•

Graph transformation

•

Even pair

•

P-4-free pair

•

Weakly Triangulated Graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
November 30, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/59451
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