The edge-connectivity conjecture for UBB cardinality

Let GG be a graph, and let λ(G)\lambda(G) denote its edge connectivity, meaning the minimum number of edges whose removal disconnects GG. For an integer tt, a tt-UBB is an uncovering-by-bases structure with parameter tt, and its cardinality is its number of spanning trees.

Edge-connectivity UBB conjecture. If

λ(G)=k,\lambda(G)=k,

then there exists a (k1)(k-1)-UBB for GG with cardinality

E(G).|E(G)|.

The conjecture is motivated by the constructions discussed in the source, where the number of spanning trees in the tt-UBB is bounded above by the number of edges. The source describes this as possibly optimistic and does not report a resolution.

Sources & referencesView supporting material

Primary source

Robert F. Bailey and Brett Stevens, “Uncoverings on graphs and network reliability”, arXiv:1012.2928 (2011).

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.