G-2023-59
Graphs obtained by disjoint unions and joins of cliques and stable sets
BibTeX reference
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.
Published December 2023 , 5 pages
Research Axes
Research applications
- Economy and finance
- Energy, environment and natural resources
- Smart infrastructure (telecommunications, public transport, smart cities)
- Engineering (engineering design, digital design)
- Smart logistics (schedule design, supply chains, logistics, manufacturing systems)
- Marketing (business intelligence, revenue management, recommendation systems)
- Health