Some properties of semiregular cages
Camino Balbuena, Xavier Marcote, Diego González-Moreno
Abstract
A graph is said to be semiregular if it has degree set
$\{r,r+1\}$. \emph{A semiregular cage} is a semiregular graph with given girth $g$ and the least possible order. First, an upper bound on the diameter of semiregular graphs with girth $g$ and order close enough to the minimum possible value is given in this work. As a consequence, these graphs are proved to be
maximally connected when the girth $g\ge 7$ is odd. Moreover an upper bound for the order of semiregular cages is given and, as an application, every semiregular cage with degree set $\{r,r+1\}$ is proved to be maximally connected for $g\in \{6,8\}$, and for
$g=12$ when some of the integers $r$, $r+1$, $r+2$ is a prime power. Further it is also shown that every $(\{r,r+1\};g)$-cage is $3$-connected.
Full Text: PostScript PDF