Bipartite structure conjecture for edge-optimal minimally k-edge-connected graphs
Bipartite structure conjecture for edge-optimal minimally k-edge-connected graphs
Let , and let be an edge-optimal minimally -edge-connected graph of order , meaning a minimally -edge-connected graph with largest average edge-connectivity among all minimally -edge-connected graphs of order . Edge-bipartite structure conjecture. For sufficiently large, is bipartite, with partite sets the set of vertices of degree and the set of vertices of degree exceeding . The paper establishes sharp bounds and extremal structures for minimally -edge-connected graphs, while the analogous structural problem for remains open.
Sources & referencesView supporting material
Primary source
Rocío M. Casablanca, Lucas Mol and Ortrud R. Oellermann, “Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs”, arXiv:1810.01972 (2018).
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.