Article de revue (2024)
 Document en libre accès dans PolyPublie et chez l'éditeur officiel |
|
Libre accès au plein texte de ce document Version officielle de l'éditeur Conditions d'utilisation: Creative Commons: Attribution (CC BY) Télécharger (275kB) |
Abstract
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
| Département: | Département de mathématiques et de génie industriel |
|---|---|
| Centre de recherche: | GERAD - Groupe d'études et de recherche en analyse des décisions |
| URL de PolyPublie: | https://publications.polymtl.ca/58906/ |
| Titre de la revue: | RAIRO - Operations Research (vol. 58, no 3) |
| Maison d'édition: | EDP Sciences |
| DOI: | 10.1051/ro/2024108 |
| URL officielle: | https://doi.org/10.1051/ro/2024108 |
| Date du dépôt: | 29 juil. 2024 13:39 |
| Dernière modification: | 08 févr. 2025 09:01 |
| 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 |
