The edge-connectivity conjecture for UBB cardinality
The edge-connectivity conjecture for UBB cardinality
Let be a graph, and let denote its edge connectivity, meaning the minimum number of edges whose removal disconnects . For an integer , a -UBB is an uncovering-by-bases structure with parameter , and its cardinality is its number of spanning trees.
Edge-connectivity UBB conjecture. If
then there exists a -UBB for with cardinality
The conjecture is motivated by the constructions discussed in the source, where the number of spanning trees in the -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
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.