Loading...
research article
Graph Transformations preserving the stability number
Lévêque, Benjamin
•
de Werra, Dominique
We analyze the relations between several graph transformations that were introduced to be used in procedures determining the stability number of a graph. We show that all these transformations can be decomposed into a sequence of edge deletions and twin deletions. We also show how some of these transformations are related to the notion of even pair introduced to color some classes of perfect graphs. Then, some properties of edge deletion and twin deletion are given and a conjecture is formulated about the class of graphs for which these transformations can be used to determine the stability number. (C) 2011 Elsevier B.V. All rights reserved.
Type
research article
Web of Science ID
WOS:000310667700025
Authors
Lévêque, Benjamin
•
de Werra, Dominique
Publication date
2012
Publisher
Published in
Volume
160
Start page
2752
End page
2759
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
February 27, 2013
Use this identifier to reference this record