Coalition graphs of connected domination partitions in subcubic graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915479054974976 |
|---|---|
| author | Dobrynin, Andrey A. Glebov, Aleksey N. |
| author_facet | Dobrynin, Andrey A. Glebov, Aleksey N. |
| contents | 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) = \{V_1, V_2,..., V_k \}$, such that each $V_i$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04204 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Coalition graphs of connected domination partitions in subcubic graphs Dobrynin, Andrey A. Glebov, Aleksey N. Combinatorics 05C69 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) = \{V_1, V_2,..., V_k \}$, such that each $V_i$ 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. |
| title | Coalition graphs of connected domination partitions in subcubic graphs |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2509.04204 |