(\(\delta ,g\))-cages with \(g\geqslant 10\) are 4-connected (Q2569934)

From MaRDI portal
scientific article
Language Label Description Also known as
English
(\(\delta ,g\))-cages with \(g\geqslant 10\) are 4-connected
scientific article

    Statements

    (\(\delta ,g\))-cages with \(g\geqslant 10\) are 4-connected (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    24 October 2005
    0 references
    A \((\delta,g)\)-cage is a \(\delta\)-regular graph with girth \(g\) having the least possible number of vertices. In 1997, \textit{H. L. Fu, K. C. Huang} and \textit{C. A. Rodger} [J. Graph Theory 24, 187--191 (1997; Zbl 0866.05035)] proved that all cages are 2-connected, and they proposed the conjecture that every \((\delta,g)\)-cage is \(\delta\)-connected. \textit{T. Jiang} and \textit{D. Mubayi} [J. Graph Theory 29, 35--44 (1998; Zbl 0919.05038)] as well as \textit{M. Daven} and \textit{C. A. Rodger} [Discrete Math. 199, 207--215 (1999; Zbl 0927.05050)] have proved that every \((\delta,g)\)-cage is 3-connected for \(\delta\geq 3\), and \textit{B. Xu, P. Wang} and \textit{J. Wang} [Ars Comb. 64, 181--192 (2002; Zbl 1071.05546)] have shown that every \((4,g)\)-cage is 4-connected. In this paper, the authors prove that every \((\delta,g)\)-cage is 4-connected provided that either \(\delta=4\) or \(\delta\geq 5\) and \(g\geq 10\).
    0 references
    0 references
    0 references
    cage
    0 references
    connectivity, regular graph
    0 references
    girth
    0 references
    0 references