The Connected Domatic Number of Fullerene Graphs Is at Most Two: A Reformulation via Induced Paths and Cycles

Document Type : Research article

Author

Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan, I. R. Iran

Abstract

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.

Keywords

Main Subjects



Articles in Press, Accepted Manuscript
Available Online from 17 November 2026
  • Receive Date: 07 October 2026
  • Revise Date: 01 November 2026
  • Accept Date: 09 November 2026
  • Publish Date: 17 November 2026