Coalition graphs of connected domination partitions in subcubic graphs Full article
| Journal |
Communications in Combinatorics and Optimization
ISSN: 2538-2128 , E-ISSN: 2538-2136 |
||
|---|---|---|---|
| Output data | Year: 2026, DOI: 10.22049/cco.2026.31013.2710 | ||
| Tags | domination in graphs, coalition graph, subcubic graph | ||
| Authors |
|
||
| Affiliations |
|
Funding (1)
| 1 | Министерство науки и высшего образования РФ | FWNF-2026-0011 |
Abstract:
A graph is subcubic if it is connected and its maximum vertex degree does not exceed 3. Two disjoint vertex subsets of a graph G form a connected coalition in G if neither of them is a connected dominating set but their union is a connected dominating set. A connected coalition partition of G is a partition of its vertices π(G), such that each set of π(G) is either a connected dominating set consisting of a single vertex or forms a coalition with some set of π(G). The formation of connected coalitions is described by a coalition graph whose vertices correspond to the sets of π, and two vertices are adjacent if and only if the corresponding sets form a coalition in G. We characterize all coalition graphs of subcubic graphs.
Cite:
Dobrynin A.A.
, Glebov A.N.
Coalition graphs of connected domination partitions in subcubic graphs
Communications in Combinatorics and Optimization. 2026. DOI: 10.22049/cco.2026.31013.2710
Coalition graphs of connected domination partitions in subcubic graphs
Communications in Combinatorics and Optimization. 2026. DOI: 10.22049/cco.2026.31013.2710
Dates:
| Submitted: | Sep 18, 2025 |
| Accepted: | Feb 18, 2026 |
| Published online: | May 25, 2026 |
Identifiers:
No identifiers