Abstract
A (k; g)-graph is a k-regular graph with girth g. Let f(k; g) be the smallest integer v such there exists a (k; g)-graph with v vertices. A (k; g)-cage is a (k; g)-graph with f(k; g) vertices. In this paper we prove that the cages are monotonic in that f(k; g1) < f(k; g2) for all k ≥ 3 and 3 ≤ g1 ≤ g2. We use this to prove that (k; g)-cages are 2-connected, and if k = 3 then their connectivity is k.
Original language | English |
---|---|
Pages (from-to) | 187-191 |
Number of pages | 5 |
Journal | Journal of Graph Theory |
Volume | 24 |
Issue number | 2 |
DOIs | |
State | Published - 1 Jan 1997 |