Discrete Mathematics & Theoretical Computer Science, Vol 12, No 5 (2010)

Font Size:  Small  Medium  Large

Some properties of semiregular cages

Camino Balbuena, Xavier Marcote, Diego González-Moreno


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