The edge domination conjecture for connected regular graphs
Let be a finite, simple, connected, -regular graph of order , where . The edge domination conjecture asserts that
Equality holds if and only if has a spanning subgraph that is the union of an odd number of copies of . 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
- 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.