A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.10783
curl -X POST /api/v1/records/arxiv/2609.10783/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.10783/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'