The edge domination conjecture for connected regular graphs
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.
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
Sign in to submit a solution.
No solutions have been posted yet.