The edge-connectivity conjecture for UBB cardinality

About 16 years old · traced to

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 (k−1)(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.

References

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.