A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture

Source abstract

Baste, Furst, Henning, Mohr, and Rautenbach conjectured that every finite regular graph of positive degree satisfies $γ(G) \leq γ_e(G)$, where $γ$ is the domination number and $γ_e$ is the edge domination number, equivalently the minimum cardinality of a maximal matching. We show that the conjecture is false already for cubic graphs. The counterexample is a previously public 50-vertex cubic graph that had been used to refute the stronger independent-domination inequality $i(G) \leq γ_e(G)$. For this graph we prove $γ(G) = 16 > 15 = γ_e(G)$. The equality $γ_e(G) = 15$ has a short counting proof, and a dominating set of order 16 is displayed explicitly. For the lower bound $γ(G) \geq 16$, we give a self-contained exact reduction: after fixing which of the 20 clause vertices lie in a putative dominating set, the remaining problem is a finite set-cover problem on the 30 literal vertices. We enumerate all $2^{20} = 1,048,576$ clause subsets, derive two explicit lower bounds, and solve exactly the 5,931 residual cases by a recurrence stated in the paper. The complete case counts and minima are displayed, and a short standard-library Python implementation is included in an appendix. A separate 893,049-node proof-tree certificate and a direct graph search provide independent verification. Thus the regular-graph conjecture is disproved. Combined with Gupta's recent theorem that every cubic graph on at most 48 vertices satisfies the conjectured inequality, the example is order-minimal among cubic counterexamples.