Coalition graphs of connected domination partitions in subcubic graphs

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 $\pi (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 $\pi (G)$. The formation of connected coalitions is described by a coalition graph whose vertices correspond to the sets of $\pi$, 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.

arXiv comment16 pages, 7 figures, 3 tables