The connected domatic number $d_c(G)$ of a graph $G$ is the largest number of pairwise disjoint connected dominating sets into which $V(G)$ can be partitioned. Connected dominating sets model backbones in communication networks, so $d_c$ counts how many disjoint backbones a network can carry. We show that a connected cubic graph has $d_c=4$ only for $K_4$, $d_c=3$ only on six vertices, and $d_c\le2$ otherwise; hence every fullerene graph satisfies $d_c\le2$. For cubic graphs of order at least $8$, $d_c=2$ holds exactly when the vertex set splits into two sets inducing paths or cycles, and these sets differ in size by at most two. Using this characterization, we give explicit splittings for the dodecahedron, which has exactly $90$ of them, for the truncated icosahedron $C_{60}$, and for the infinite family of $(5,0)$ nanotube fullerenes. An exhaustive search covers all fullerenes on at most $36$ vertices. Whether $d_c=2$ for every fullerene remains a conjecture.
Fath-Tabar, G. H. (2026). The Connected Domatic Number of Fullerene Graphs Is at Most Two: A Reformulation via Induced Paths and Cycles. Analytical and Numerical Solutions for Nonlinear Equations, (), -. doi: 10.22128/ansne.2026.3506.1250
MLA
Gholam Hossein Fath-Tabar. "The Connected Domatic Number of Fullerene Graphs Is at Most Two: A Reformulation via Induced Paths and Cycles", Analytical and Numerical Solutions for Nonlinear Equations, , , 2026, -. doi: 10.22128/ansne.2026.3506.1250
HARVARD
Fath-Tabar, G. H. (2026). 'The Connected Domatic Number of Fullerene Graphs Is at Most Two: A Reformulation via Induced Paths and Cycles', Analytical and Numerical Solutions for Nonlinear Equations, (), pp. -. doi: 10.22128/ansne.2026.3506.1250
VANCOUVER
Fath-Tabar, G. H. The Connected Domatic Number of Fullerene Graphs Is at Most Two: A Reformulation via Induced Paths and Cycles. Analytical and Numerical Solutions for Nonlinear Equations, 2026; (): -. doi: 10.22128/ansne.2026.3506.1250