The edge domination conjecture for connected regular graphs

From papers

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.

Progress summary

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

Sources & referencesView supporting material

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).

Solutions 0

No solutions have been posted yet.