Paired Domination in Cubic Bipartite Graphs

A paired dominating set of a graph $G$ is a dominating set $D$ such that $G[D]$ has a perfect matching. The minimum size of such a set is the paired domination number $\text{gpr}(G)$. Desormeaux and Henning conjectured that every cubic bipartite graph $G$ of order $n$ satisfies $\text{gpr}(G)\le n\mathrm{/}2$. We prove the conjecture in the sharp integer form $\text{gpr}(G)\le 2\lfloor \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}4\rfloor$ for every finite simple cubic bipartite graph $G$. The proof combines a directed contraction along a perfect matching, switching arguments based on dominator trees, a four-symbol boundary calculus for two-edge cuts, and the Gallai–Edmonds decomposition. Equality is attained by $K_{3,3}$ when $\mathrm{\mid }V(G)\mathrm{\mid }\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}4)$ and by the cube $Q_3$ when $\mathrm{\mid }V(G)\mathrm{\mid }\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}4)$.