Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649346 | Discrete Mathematics | 2009 | 7 Pages |
Abstract
S. Smith conjectured that any two distinct longest cycles of a kk-connected graph must meet in at least kk vertices when k≥2k≥2. Here we provide evidence for the dual version of the Smith conjecture: if CC and DD are largest bonds in a kk-connected graph GG, then the number of components in G−(C∪D)G−(C∪D) is at least k+2−|C∩D|k+2−|C∩D|. Both conjectures have been proven only for small kk. This article establishes a linear lower bound on the number of components of G−(C∪D)G−(C∪D) which holds for all values of k≥7k≥7. This is stronger than the best bound established to date for Smith’s original conjecture.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Laura Sheppardson,