Clique-width of graphs defined by one-vertex extensions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2008

Clique-width of graphs defined by one-vertex extensions

Michaël Rao

Résumé

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.

Mots clés

Fichier non déposé

Dates et versions

lirmm-00808032 , version 1 (04-04-2013)

Identifiants

Citer

Michaël Rao. Clique-width of graphs defined by one-vertex extensions. Discrete Mathematics, 2008, 308, pp.6157-6165. ⟨10.1016/j.disc.2007.11.039⟩. ⟨lirmm-00808032⟩
114 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More