Clique-width of graphs defined by one-vertex extensions

Michaël Rao 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Let G be a graph and u be a vertex of G . We consider the following operation: add a new vertex v such that v does not distinguish any two vertices which are not distinguished by u . We call this operation a one-vertex extension. Adding a true twin, a false twin or a pendant vertex are cases of one-vertex extensions. Here we are interested in graph classes defined by a subset of allowed one-vertex extension. Examples are trees, cographs and distance-hereditary graphs. We give a complete classification of theses classes with respect to their clique-width. We also introduce a new graph parameter called the modular-width, and we give a relation with the clique-width.
Keywords : Clique-width
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2008, 308, pp.6157-6165. 〈10.1016/j.disc.2007.11.039〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00808032
Contributeur : Pascal Ochem <>
Soumis le : jeudi 4 avril 2013 - 17:14:16
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Michaël Rao. Clique-width of graphs defined by one-vertex extensions. Discrete Mathematics, Elsevier, 2008, 308, pp.6157-6165. 〈10.1016/j.disc.2007.11.039〉. 〈lirmm-00808032〉

Partager

Métriques

Consultations de la notice

102