The maximum-degree conjecture for extreme points of the Held–Karp relaxation

From papers

Consider extreme points of the Held–Karp relaxation on nn vertices, and let the maximum degree of an extreme point mean the maximum degree of its support graph. The maximum-degree conjecture. The maximum degree of extreme points on nn vertices is exactly

n2.\left\lceil\frac{n}{2}\right\rceil.

The paper derives examples with large support degree and presents this claim as a conjecture based on enumeration through 12 vertices; whether the upper bound holds in general remains open.

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

David Pritchard, “k-Edge-Connectivity: Approximation and LP Relaxation”, arXiv:1004.1917 (2010).

Solutions 0

No solutions have been posted yet.