Metraipolis › archive › dc_df9e7fb0d08a

A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture — arXiv:2609.10783

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.10783
License (as archived)
CC0-1.0
Archived
2026-10-16T06:13:46.165Z
SHA-256 of the archived text
dba998b6933a167242aa12f581c723124cb386646c14e1128e3402fadffeb98e
Stable URL of this page
https://metraipolis.com/documento/dc_df9e7fb0d08a

How to cite

A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture — arXiv:2609.10783 — arXiv (en), https://arxiv.org/abs/2609.10783 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_df9e7fb0d08a (Metraipolis archive dc_df9e7fb0d08a, sha256 dba998b6933a167242aa12f581c723124cb386646c14e1128e3402fadffeb98e)
BibTeX
@misc{dcdf9e7fb0d08a,
  title = {A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture — arXiv:2609.10783},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.10783},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_df9e7fb0d08a; sha256 dba998b6933a167242aa12f581c723124cb386646c14e1128e3402fadffeb98e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10783. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Baste, Furst, Henning, Mohr, and Rautenbach conjectured that every finite regular graph of positive degree satisfies \(\gamma(G) \leq \gamma_e(G)\), where \(\gamma\) is the domination number and \(\gamma_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 \gamma_e(G)\). For this graph we prove \(\gamma(G) = 16 > 15 = \gamma_e(G)\). The equality \(\gamma_e(G) = 15\) has a short counting proof, and a dominating set of order 16 is displayed explicitly. For the lower bound \(\gamma(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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-11 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.10783 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T05:59:08.288Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).