Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9512360 | Discrete Mathematics | 2005 | 13 Pages |
Abstract
A regular graph G of degree δ and girth g is said to be a (δ,g)-cage if it has the least number of vertices among all δ-regular graphs with girth g. A graph is called k-connected if the order of every cutset is at least k. In this work, we prove that every (δ,g)-cage is 4-connected provided that either δ=4, or δ⩾5 and g⩾10. These results support the conjecture of Fu, Huang and Rodger that all (δ,g)-cages are δ-connected.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
X. Marcote, C. Balbuena, I. Pelayo, J. FÃ brega,