Bipartite structure conjecture for edge-optimal minimally k-edge-connected graphs

Let k3k\geq 3, and let GG be an edge-optimal minimally kk-edge-connected graph of order nn, meaning a minimally kk-edge-connected graph with largest average edge-connectivity among all minimally kk-edge-connected graphs of order nn. Edge-bipartite structure conjecture. For nn sufficiently large, GG is bipartite, with partite sets the set of vertices of degree kk and the set of vertices of degree exceeding kk. The paper establishes sharp bounds and extremal structures for minimally 22-edge-connected graphs, while the analogous structural problem for k3k\geq 3 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

Never refreshed

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.