Intersections of largest bonds (minimal edge cuts)
by
Laura Sheppardson
University of Mississippi

A well-known conjecture of Scott Smith states that any two distinct longest cycles of a k-connected graph must meet in at least k vertices when k ≥ 2. Generalizing this conjecture to matroids yields the dual version: If C and D are largest bonds in a k-connected graph G, then the number of components in G - (C ∪D) is at least k+2-|C ∩D|. Both conjectures have been proven only for small k. We present a linear lower bound on the number of components of G - (C ∪D) which holds for all values of k. This is stronger than the best bound established to date for Smith's original conjecture.

Date received: April 18, 2008