A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture
Abstract
Baste, Furst, Henning, Mohr, and Rautenbach conjectured that every finite regular graph of positive degree satisfies γ(G) ≤ γ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) ≤ γ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) ≥ 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 220 = 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.
Related
- A Counterexample to an Eternal Domination Conjecture
- A counterexample to vertex interpolation by planar C1 cubic splines
- A symmetric counterexample to Strang's conjecture for bivariate C1 cubic splines on triangulations
- Graphs with Large Vertex–Edge Roman {2}-Domination Number
- Vertex Removal and Vertex-Edge Domination
BibTeX
@misc{afrasyab202650vertex,
title = {{A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture}},
author = {Koyar Afrasyab},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10783},
eprint = {2609.10783},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10783},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture
AU - Koyar Afrasyab
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10783
UR - https://arxiv.org/abs/2609.10783
AB - Baste, Furst, Henning, Mohr, and Rautenbach conjectured that every finite regular graph of positive degree satisfies γ(G) ≤ γ_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) ≤ γ_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) ≥ 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.
ER -