The edge domination conjecture for connected regular graphs

About 7 years old · traced to

Let GG be a finite, simple, connected, Δ\Delta-regular graph of order nn, where Δ≥3\Delta\geq 3. The edge domination conjecture asserts that

γe(G)≤2Δ−14Δn+12.\gamma_e(G)\leq \frac{2\Delta-1}{4\Delta}n+\frac{1}{2}.

Equality holds if and only if GG has a spanning subgraph that is the union of an odd number of copies of KΔ,Δ−eK_{\Delta,\Delta}-e. This conjecture would give a best-possible upper bound on the minimum size of a maximal matching in connected regular graphs, with an explicit characterization of the equality cases.

References

Primary source

Julien Baste, Maximilian Fürst, Michael A. Henning, Elena Mohr and Dieter Rautenbach, “Bounding and approximating minimum maximal matchings in regular graphs”, arXiv:1905.12241 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.