G-2023-59
Graphs obtained by disjoint unions and joins of cliques and stable sets
référence BibTeX
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.
Paru en décembre 2023 , 5 pages
Axes de recherche
Applications de recherche
- Économie et finance
- Énergie, environnement, ressources naturelles
- Infrastructures intelligentes (télécommunications, transport public, villes intelligentes)
- Ingénierie (conception en ingénierie, conception numérique)
- Logistique intelligente (conception d’horaires, chaînes d’approvisionnement, logistique, systèmes manufacturiers)
- Marketing (intelligence d’affaires, gestion des revenus, systèmes de recommandation)
- Santé
Publication
juin 2024
RAIRO - Operations Research, 58(3), 2631–2636, 2024
référence BibTeX