Graphs obtained by disjoint unions and joins of cliques and stable sets

Alain Hertz

Article de revue (2024)

Accéder à ce document
Disponible
Libre accès au texte intégral dans PolyPublie et chez l'éditeur officiel
Version officielle de l'éditeur
Texte Texte • 275kB •

Résumé

We consider the set of graphs that can be constructed from a one-vertex graph by repeatedly adding a clique or a stable set linked to all or none of the vertices added in previous steps. This class of graphs contains various well-studied graph families such as threshold, domishold, co-domishold and complete multipartite graphs, as well as graphs with linear clique-width at most 2. We show that it can be characterized by three forbidden induced subgraphs as well as by properties involving maximal stable sets and minimal dominating sets. We also give a simple recognition algorithm and formulas for the computation of the stability and domination numbers of these graphs.

Mots clés

Adresse URL de PolyPublie:
Titre de la revue :
RAIRO - Operations Research ( vol. 58 , no 3 )
Maison d'édition:
EDP Sciences
OAI:
oai:publications.polymtl.ca:58906
ORCID
Date du dépôt:
29 juil. 2024 13:39
Dernière modification:
14 oct. 2026 14:19
Citer en APA 7:
Hertz, A. (2024). Graphs obtained by disjoint unions and joins of cliques and stable sets. RAIRO - Operations Research, 58(3), 2631-2636. https://doi.org/10.1051/ro/2024108

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Dimensions

Actions réservées au personnel

Afficher document
Afficher document