The extremal matching conjecture for almost alternating threshold graphs
The extremal matching conjecture for almost alternating threshold graphs
Let . Let be an almost alternating threshold graph, and let be a threshold graph with the same number of vertices and edges as . Write for the number of matchings of size in a graph . Extremal matching conjecture. Then
In addition, if , , and is not almost alternating, then
The paper establishes that almost alternating threshold graphs maximize the total number of matchings, but its methods do not extend to matchings of a fixed size . Computer testing through vertices supports this stronger fixed-size assertion, which remains open.
Sources & referencesView supporting material
Primary source
L. Keough and A. J. Radcliffe, “Extremal Threshold Graphs for Matchings and Independent Sets”, arXiv:1710.00083 (2017).
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
Sign in to submit a solution.
No solutions have been posted yet.