Article (2024)
 Open Acess document in PolyPublie and at official publisher |
|
Open Access to the full text of this document Published Version Terms of Use: Creative Commons Attribution Download (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.
Uncontrolled Keywords
| Subjects: | 2950 Applied mathematics > 2950 Applied mathematics |
|---|---|
| Department: | Department of Mathematics and Industrial Engineering |
| Research Center: | GERAD - Research Group in Decision Analysis |
| PolyPublie URL: | https://publications.polymtl.ca/58906/ |
| Journal Title: | RAIRO - Operations Research (vol. 58, no. 3) |
| Publisher: | EDP Sciences |
| DOI: | 10.1051/ro/2024108 |
| Official URL: | https://doi.org/10.1051/ro/2024108 |
| Date Deposited: | 29 Jul 2024 13:39 |
| Last Modified: | 08 Feb 2025 09:01 |
| Cite in 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 |
|---|---|
Statistics
Total downloads
Downloads per month in the last year
Origin of downloads
Dimensions
Repository Staff Only
|
View Item |
