(δ,g)-cages with g⩾10 are 4-connected

Autor: J. Fíbrega, Camino Balbuena, X. Marcote, Ignacio M. Pelayo
Rok vydání: 2005
Předmět:
Zdroj: Discrete Mathematics. 301:124-136
ISSN: 0012-365X
DOI: 10.1016/j.disc.2004.11.026
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: