Graph Transformations Preserving the Stability Number

Benjamin Lévêque 1 Dominique De Werra 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We analyse 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.
Type de document :
Communication dans un congrès
LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2009, Gramado, Brazil. V Latin-American Algorithms, Graphs and Optimization Symposium, pp.3-8, 2009, Electronic Notes in Discrete Mathematics
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00620722
Contributeur : Benjamin Lévêque <>
Soumis le : jeudi 8 septembre 2011 - 14:20:32
Dernière modification le : mercredi 3 octobre 2018 - 15:16:02

Identifiants

  • HAL Id : lirmm-00620722, version 1

Collections

Citation

Benjamin Lévêque, Dominique De Werra. Graph Transformations Preserving the Stability Number. LAGOS: Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2009, Gramado, Brazil. V Latin-American Algorithms, Graphs and Optimization Symposium, pp.3-8, 2009, Electronic Notes in Discrete Mathematics. 〈lirmm-00620722〉

Partager

Métriques

Consultations de la notice

122