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