Loading...
research article
A Magnetic Procedure for the Stability Number
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.
Type
research article
Web of Science ID
WOS:000274852300005
Authors
Publication date
2009
Published in
Volume
25
Start page
707
End page
716
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
November 30, 2010
Use this identifier to reference this record