2025/09/04 by Dobrynin, Andrey A., Glebov, Aleksey N. · 1 citation
#05C69 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.04204
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) = \V1, V2,..., Vk \, such that each Vi 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.