Loading...
Loading...

Go to the content (press return)

(d,g)-cages with g >= 10 are 4-connected

Author
Marcote, F.; Pelayo, I. M.; Balbuena, C.; Fàbrega, J.
Type of activity
Journal article
Journal
Discrete mathematics
Date of publication
2005-09
Volume
301
Number
1
First page
124
Last page
136
DOI
https://doi.org/10.1016/j.disc.2004.11.026 Open in new window
URL
http://dx.doi.org/10.1016/j.disc.2004.11.026 Open in new window
Abstract
A regular graph G of degree d and girth g is said to be a (d,g)-cage if it has the least number of vertices among all d-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 (d,g)-cage is 4-connected provided that either d=4, or d¿5 and g¿10. These results support the conjecture of Fu, Huang and Rodger that all (d,g)-cages are d-connected.
Keywords
Cage, Connectivity, Cutset
Group of research
COMBGRAPH - Combinatorics, Graph Theory and Applications