Paired Domination in Cubic Bipartite Graphs

Changhong Lu; Qi Wu

In the authors' words

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 $\gpr (G)$ . Desormeaux and Henning conjectured that every cubic bipartite graph $G$ of order $n$ satisfies $\gpr (G) \leq n /2$ . We prove the conjecture in the sharp integer form $\gpr (G) \leq 2 ⌊ ∣ V (G) ∣/4 ⌋$ 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 $∣ V (G) ∣ \equiv 2 (mod 4)$ and by the cube $Q_{3}$ when $∣ V (G) ∣ \equiv 0 (mod 4)$ .

Main resultThe abstract does not state a limitation.

Paired Domination in Cubic Bipartite Graphs

In the authors' words

More on Combinatorics & discrete math that day

Thinning and sprinkling: from robust sampling to almost Hamiltonicity

Boolean threshold functions, neuron capacity, and memory retrieval

The Marcus-Minc Transform Inequality

The coarse Erd\H{o}s-P\'{o}sa theorem

A Combinatorial Proof of Hilton's Conjecture and Beyond