Scott Smith conjectured in 1979 that distinct longest cycles of a k-connected graph meet in at least k vertices when k ≥ 2. This conjecture is still open. Reid and Wu generalized the conjecture to matroids by considering largest circuits. An equivalent conjecture in terms of largest cocircuits is given here. The specialization of this conjecture to graphs is then obtained. This specialization involves largest bonds in a graph.; The general conjecture about largest circuits in a k-connected matroid was solved by Seymour for the case k = 2. We provide an attractive generalization of this result for circuits that are almost largest circuits. In addition, we prove the general conjecture for the class of uniform matroids and the class of matroids with largest circuit size at most four. The main result of this dissertation establishes the general conjecture for k-connected cographic matroids when k ≤ 5. This provides a dual result to the establishment of Smith's conjecture for k ≤ 10 as reported by Grotschel. Several related results on largest bonds in graphs are also given.
展开▼