Article ID Journal Published Year Pages File Type
4649346 Discrete Mathematics 2009 7 Pages PDF
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.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,