# Perturbative study of the one dimensional quantum clock model

Bingnan Zhang<EMAIL_ADDRESS>Department of Physics, Rutgers New
Brunswick, NJ 08854, USA

###### Abstract

We calculate the ground state energy density $\epsilon(g)$ for the one
dimensional N-state quantum clock model up to order 18, where $g$ is the
coupling and $N=3,4,5,...,10,20$. Using methods based on Padé approximation,
we extract the singular structure of $\epsilon^{\prime\prime}(g)$ or
$\epsilon(g)$. They correspond to the specific heat and free energy of the
classical 2D clock model[12]. We find that, for $N=3,4$, there is a single
critical point at $g_{c}=1$.The heat capacity exponent of the corresponding 2D
classical model is $\alpha=0.34\pm 0.01$ for $N=3$, and $\alpha=-0.01\pm 0.01$
for $N=4$. For $N>4$, There are two exponential singularities related by
$g_{c1}=1/g_{c2}$, and $\epsilon(g)$ behaves as
$Ae^{-\frac{c}{|g_{c}-g|^{\sigma}}}+analytic\ terms$ near $g_{c}$. The
exponent $\sigma$ gradually grows from $0.2$ to $0.5$ as N increases from 5 to
9, and it stabilizes at 0.5 when $N>9$. The phase transitions exhibited in
these models should be generalizations of Kosterlitz-Thouless transition,
which has $\sigma=0.5$.

##  I Introduction

The classical 2D N-state clock model is a generalization of the Ising model.
When $N=2$, it is the Ising model, and it becomes the XY model when
$N\rightarrow\infty$. It is widely believed that for $N\leq 4$ there is a
second order phase transition as we dial up the temperature from zero, while
there are two BKT-like transitions for $N>4$[1][2][3][4][5]. However, the
quantitative behavior of the free energy for $N>4$ is still controversial . In
an early paper [1], the singular part of the free energy was argued to behave
like $e^{-\frac{c}{|T_{c}-T|^{\sigma}}}$ near $T_{c}$, where $\sigma\approx
0.22$ for $N=5$, $\sigma\approx 0.5$ for $N>5$. More recent simulations
indicate that $\sigma=0.5$ for $N=5$ [10]. There are also simulations that
claim to show that the transition in $N=5$ model is not BKT-like [11]. In this
paper, we will try to shed some light on these questions by studying the 1D
quantum clock model, whose ground state energy energy maps to the free energy
of the corresponding 2D classical model [12].

The paper is organized as the follows: section II specifies the model. Section
III discusses the linked cluster expansion, which is the method used in
calculating the series. The codes used in this section can be downloaded at
https://github.com/beyondoubt3/clock-model-perturbation. Section IV introduces
Padé approximation and its improvements. Section V includes the series and
fitting results and section VI is a summary. Readers who are familiar with the
linked cluster expansion, Padé approximations and inhomogeneous differential
approximations can go directly to section V.

##  II The model

The Hamiltonian is

$H=-g\sum_{i}(V_{i}+V_{i}^{\dagger})-\sum_{i}(U_{i}U_{i+1}^{\dagger}+U_{i+1}U_{i}^{\dagger})$
(1)

where $i$ runs over all sites on the one dimensional lattice, and we use
periodic boundary conditions.

$V_{i}=\begin{pmatrix}0&1&0&...&0\\\ 0&0&1&...&0\\\ \vdots&\vdots&\vdots&\
&\vdots\\\ 0&0&0&...&1\\\ 1&0&0&...&0\end{pmatrix}\ \
U_{i}=\begin{pmatrix}1&0&0&...&0\\\ 0&e^{\frac{2\pi i}{N}}&0&...&0\\\
0&0&e^{\frac{4\pi i}{N}}&...&0\\\ \vdots&\vdots&\vdots&\ &\vdots\\\
0&0&0&...&e^{\frac{2\pi(N-1)i}{N}}\end{pmatrix}$ (2)

are generators of the finite Heisenberg group, and they satisfy

$V_{i}U_{i}=\omega U_{i}V_{i},\ \omega=e^{i\frac{2\pi}{N}}$ (3)

Working in the basis where $U_{i}$ operators are diagonal, the effect of
$U_{i}$ is to read the needle’s position on the $i$th clock, and $V_{i}$ dials
up the needle by one unit (figure 1).

i-1ii+1 Figure 1: The clock model.

In the limit $g\rightarrow 0$, every clock’s needle is locked at the same
position, and there is a $N-fold$ degeneracy. The perturbation won’t mix any
two of them when the order of perturbation theory is small compared to the
lattice size, so we can arbitrarily choose one as our starting point. Once the
starting point is chosen, we can relabel the states by the difference in
position between two nearest neighbor clocks. To be more precise, define
$u_{i},\ v_{i}$ such that

$u_{i}=U_{i}U_{i+1}^{\dagger},\ V_{i}=v_{i-1}^{\dagger}v_{i}$ (4)

where $u_{i},\ v_{i}$ have the same matrix representations as $U_{i},\ V_{i}$.
Figure 2 is an example of state relabeling. The first line labels the state by
eigenvalues of $U_{i}$ while the second line labels the state by eigenvalues
of $u_{i}$:

i-1ii+1$e^{i\frac{2\pi n}{N}}$$e^{i\frac{2\pi m}{N}}$$e^{i\frac{2\pi l}{N}}$

$\bigg{\downarrow}$

i-1i$e^{i\frac{2\pi(n-m)}{N}}$$e^{i\frac{2\pi(m-l)}{N}}$

Figure 2: State relabeling.

Now we do a second relabeling. Since

$v_{i}u_{i}=\omega u_{i}v_{i},\ \ u_{i}^{\dagger}v_{i}=\omega
v_{i}u_{i}^{\dagger}$ (5)

We can relabel

$u_{i}\rightarrow v_{i},\ \ v_{i}\rightarrow u_{i}^{\dagger}$ (6)

After these two steps, the Hamiltonian becomes

$\displaystyle H(g)$
$\displaystyle=-g\sum_{i}(u_{i}u_{i+1}^{\dagger}+h.c.)-\sum_{i}(v_{i}+h.c.)$
(7)
$\displaystyle=g\left(-\sum_{i}(u_{i}u_{i+1}^{\dagger}+h.c.)-\frac{1}{g}\sum_{i}(v_{i}+h.c.)\right)$

Thus the ground state energy density at large $g$ and small $g$ are related by

$\epsilon(g)=g\epsilon(\frac{1}{g})$ (8)

##  III Calculating the series

The key method used here is linked cluster expansion[6]. As an analog of
Feynman diagram expansion in Field theory, linked cluster expansion states
that the perturbation series of ground state energy, or any extensive
quantities for an Hamiltonian lattice system, only receives contributions from
connected clusters of lattice sites.

$E(G)=\sum_{G^{\prime}\in G}b(G^{\prime}/G)e(G^{\prime})$ (9)

where $G$ is the cluster we are interested in, $G^{\prime}$ runs over all sub-
clusters in $G$, and $b(G^{\prime}/G)$ is the embedding number that tells us
how many ways to embed cluster $G^{\prime}$ within $G$. $e(G^{\prime})$ is the
’reduced energy’. It is different from $E(G^{\prime})$ because $E(G^{\prime})$
receive contributions from all of $G^{\prime}$’s sub-clusters while
$e(G^{\prime})$ only counts $G^{\prime}$ itself.

The good thing about linked cluster expansion is that for any finite cluster
$G^{\prime}$, the series for $e(G^{\prime})$ starts from an order proportional
to the cluster size. For example, in our model (1), the clusters are just
chains with certain lengths. If $G^{\prime}$ has length $k$, then
$e(G^{\prime})$ starts from order $2k$. This means that if we want to
calculate $E(G)$ to order $2k$, we only have to pay attention to the sub-
clusters of $G$ with size smaller than $k+1$.

In many cases, the embedding number $b$ is very difficult to evaluate.
However, for the 1D lattice considered in this paper, the embedding number is
extremely simple. Let us denote by $G_{n}$ a chain with length $n$. There are
$m-n+1$ different ways to embed a chain of length $n$ within a chain of length
$m$ ($m>n$ of course), so the embedding number of $G_{n}$ inside $G_{m}$ is

$b(G_{n}/G_{m})=m-n+1$

so equation (9) becomes

$E(G_{m})=me(G_{1})+(m-1)e(G_{2})+(m-2)e(G_{3})+...+e(G_{m})$ (10)

If we are only interested in series below order $2k$ ($k<m$), We can truncate
the above series

$\displaystyle E(G_{m})\stackrel{{\scriptstyle to\ order\ 2k}}{{=}}$
$\displaystyle me(G_{1})+(m-1)e(G_{2})+(m-2)e(G_{3})+...$ (11)
$\displaystyle+(m-k+1)e(G_{k})$

In this paper, we are interested in the ground state energy density in the
thermodynamic limit, so

$\displaystyle\frac{E(G_{m})}{m}\mathrel{\stackunder[2pt]{\stackon[4pt]{=}{$\scriptscriptstyle
to\ order\ 2k$}}{$\scriptscriptstyle m\rightarrow\infty$}}$ $\displaystyle
e(G_{1})+e(G_{2})+e(G_{3})+...+e(G_{k})$ (12) $\displaystyle=$ $\displaystyle
E(G_{k})-E(G_{k-1})$

Now the only thing left is to do perturbations on chains with length $k$ and
$k-1$ to calculate $E(G_{k})$ and $E(G_{k-1})$. Here we use the standard
Rayleigh-Schrödinger perturbation theory. We expand the ground state energy

$E^{0}=E^{0}_{0}+E^{0}_{1}+E^{0}_{2}+...$ (13)

and the ground state wavefunction

$|\Psi^{0}\rangle=|\Psi^{0}_{0}\rangle+\sum_{j>0}c_{j,1}|\Psi^{j}_{0}\rangle+\sum_{j>0}c_{j,2}|\Psi^{j}_{0}\rangle+...$
(14)

$E^{0}_{j}$ and $c_{j,r}$ can be calculated with iteration[6].

$\displaystyle E_{r}^{0}=\sum_{j}H^{\prime}_{0,j}c_{j,r-1}$ (15)
$\displaystyle
c_{j,r}=\frac{1}{E_{0}^{j}-E_{0}^{0}}(-\sum_{W}eH^{\prime}_{j,i}c_{i,r-1}+\sum_{s=0}^{r-1}E_{r-s}^{0}c_{j,s}),j\neq
0$

where $H^{\prime}_{j,i}=\langle\Psi^{j}_{0}|H^{\prime}|\Psi^{i}_{0}\rangle$
and $H^{\prime}$ is the first order part of the Hamiltonian.

The input data is the set of states $|\Psi^{j}_{0}\rangle$. One doesn’t have
to generate all states in the Hilbert space, because many of them won’t be
used. If we want to calculate the series to order $2k$, only those
$|\Psi^{j}_{0}\rangle$ that satisfy
$\langle\Psi^{j}_{0}|(H^{\prime})^{a}|\Psi^{0}_{0}\rangle\neq 0$ for a certain
integer $0<a\leq k$ will be used. Once the states are generated, the
calculation of $E_{0}^{j}$ is fast and straightforward. Calculating
$H^{\prime}_{j,i}$ is, however, time-consuming. In fact, most of the time in
this algorithm is spent on calculating $H^{\prime}_{j,i}$. The reason is that
in order to calculate $H^{\prime}_{j,i}$, a simple algorithm will run through
the states twice, roughly speaking. We believe that using some formulas in
restricted partition theory, there is a clever way to sort the states such
that one only have to run through the states once. If this is true,
significantly more orders can be obtained. The codes used in this section can
be downloaded online at https://github.com/beyondoubt3/clock-model-
perturbation.

##  IV Fitting methods

###  IV.1 Padé and DLog Padé

Instead of fitting an unknown function by its series expansion, which is a
polynomial, the Padé approximation[7] fits the function by the quotient of two
polynomials. For example, suppose

$f(g)=f_{0}+f_{1}g+f_{2}g^{2}+...+f_{s}g^{s}+O(g^{s+1}),\ g<1$ (16)

we fit $f(g)$ by the form

$f_{[n/m]}(g)=\frac{\sum_{i=0}^{n}p_{i}g^{i}}{1+\sum_{j=1}^{m}q_{j}g^{j}}$
(17)

where $n+m+1=s+1$. One solves for $p_{i},q_{j}$ by requiring that
$f=f_{[n/m]}$ below order $s+1$. Padé fitting often yield good results because
the large $g$ behavior is controlled. It is very good at capturing poles and
zeros within the convergence region, and it will mimic a branch cut by
accumulating poles and zeros along that line. However, sometimes fake poles
will appear to render the approximation inaccurate, so only those poles and
zeros which are stable when we change the orders $m,n$ of the approximant
should be trusted.. In principle, $n$ and $m$ can be any positive integer.
However, what happens most is that the fitting works best when $n$ and $m$ are
close. In many cases, one just sets $n=m$.

If we have the expansions of $f(g)$ at two points, we let $f_{[n/m]}$ agree
with those two series simultaneously, and this is called two point Padé. Of
course, one of the points can be infinity.

DLog Padé is used in extracting critical exponents. Suppose $f(g)$ goes like
$(g_{c}-g)^{-v}$ near $g_{c}$, then
$\frac{dlog(|f|)}{dg}=\frac{f^{\prime}}{f}$ goes like $\frac{-v}{g-g_{c}}$
near $g_{c}$. Since Padé approximant is particularly good at fitting poles of
order one, we can estimate $-v$ by applying Padé approximation to
$\frac{f^{\prime}}{f}$ and then calculate its residue at $g_{c}$.

###  IV.2 Inhomogeneous differential approximation
(IDA)

Sometimes DLog Padé gives a bad estimate of critical exponents. This is caused
by background terms, and IDA[8] takes that into account. We write
$f(g)=A(g)(1-\frac{g}{g_{c}})^{-v}+B(g)$ near $g_{c}$, where $A(g)$ and $B(g)$
are both analytic. $f(g)$ satisfies

$u(g)+p(g)f(g)-q(g)f^{\prime}(g)=0$ (18)

where

$\displaystyle u(g)=$
$\displaystyle(g_{c}-g)A(g)B^{\prime}(g)-[vA(g)+(g_{c}-g)A^{\prime}(g)]B(g)$
(19) $\displaystyle p(g)=$ $\displaystyle vA(g)+(g_{c}-g)A^{\prime}(g)$
$\displaystyle q(g)=$ $\displaystyle(g_{c}-g)A(g)$

In practical use, we choose $u,p,q$ to be polynomials , and solve equation(18)
order by order. $g_{c}$ can be estimated as the stable zero point of $q$, and
$v$ can be estimated as $\frac{-p^{\prime}(g_{c})}{q(g_{c})}$. When we have
both small $g$ and large $g$ series for $f(g)$, we fix the order of $u,p,q$ by
letting the three terms in equation(18) start at the same order, both in the
small $g$ and large $g$ limits. We’ve found that without these restrictions
the results are unreliable.

##  V Results

The ground state energy density series in the small $g$ limit are listed in
appendix C. The series in the large $g$ limit can be obtained by the duality
relation (8).

###  V.1 N=3,4

One can map the 1D quantum model to a 2D classical model, and $\epsilon(g)$
becomes the free energy, $\epsilon^{\prime\prime}(g)$ becomes specific heat.
It is believed that for $N=3,4$ there is a second order phase transition[1].
Table 1,2 are the results of applying single side DLog Padé fitting to
$\epsilon^{\prime\prime}(g)$ for $N=3,4$:

Polynomial type | Pole | Residue
---|---|---
$[5/6]$ | 1.00644 | -0.465541
$[4/5]$ | 1.01735 | -0.510407
$[3/4]$ | 1.01595 | -0.507258
$[2/3]$ | 1.0369 | -0.556233
Table 1: N=3 fitting $\epsilon^{{}^{\prime\prime\prime}}/\epsilon^{{}^{\prime\prime}}$ Polynomial type | Pole | Residue
---|---|---
$[6/6]$ | 1.00951 | -0.281564
$[5/5]$ | 1.01481 | -0.307984
$[4/4]$ | 1.02066 | -0.329759
$[3/3]$ | 1.04277 | -0.387972
Table 2: N=4 fitting
$\epsilon^{{}^{\prime\prime\prime}}/\epsilon^{{}^{\prime\prime}}$

In both cases the pole position stabilizes at 1, but the residue is still
changing. This is the effect of background terms. In order to improve the
estimation of the residue, we use IDA (section IV.2). The results are listed
below (table 3,4):

Polynomial type | Pole | Residue
---|---|---
u2 p5 q6 | 1.00027 | -0.339898
u4 p4 q5 | 1.00025 | -0.338126
u1 p4 q5 | 1.00098 | -0.353952
Table 3: N=3 IDA fitting $\epsilon^{{}^{\prime\prime\prime}}/\epsilon^{{}^{\prime\prime}}$ Polynomial type | Pole | Residue
---|---|---
u2 p5 q6 | 0.999829 | $0.00716088$
u5 p4 q4 | 0.999509 | $0.019595$
u4 p5 q4 | 0.999637 | $0.0148813$
Table 4: N=4 IDA fitting
$\epsilon^{{}^{\prime\prime\prime}}/\epsilon^{{}^{\prime\prime}}$

’u5 p8 q9’ means we set

$u=\sum_{i=0}^{5}u_{i}g^{i},p=\sum_{i=0}^{8}p_{i}g^{i},q=1+\sum_{i=1}^{9}q_{i}g^{i}$

.

A summary of the above results: both $N=3,N=4$ models have a single critical
point at $g_{c}=1$. The specific heat exponent $\alpha$ for the corresponding
2D classical model is estimated as $0.34\pm 0.01$ for $N=3$, and $-0.01\pm
0.01$ for $N=4$. As we know, the 3-state clock model is equivalent to the
3-state Potts model[13], and the 4-state clock model is equivalent to two
copies of the Ising model at the critical point[14]. Both of them are exactly
solvable:$\alpha=1/3$ for $N=3$ and $\alpha=0$ for $N=4$[13]. Comparing to
these exact results, our estimates are fairly reasonable. We notice that in an
early paper [9], the series for the 3-state model was calculated to order 31,
and $\alpha$ was estimated with DLog Padé method. Their results never
stabilize, which is consistent with what we found at first. The IDA method is
thus a significant improvement.

One can further refine the result for $N=4$ by using the two point IDA, using
both small g series and large g series. However, the two point method doesn’t
work very well for the $N=3$ model.

###  V.2 N$>$4

For $N>4$ we expect to see two essential singularities related by
$g_{c_{1}}=1/g_{c_{2}}$, and the singular part of free energy is
$e^{-\frac{c}{|g_{c}-g|^{\sigma}}}$[1]. When $N\rightarrow\infty$ the model
maps to the classical XY model in 2D, $\sigma=0.5$. In order to find the
critical point, we take a derivative. $\epsilon^{\prime}(g)$ approaches zero
like $-\frac{A}{(g_{c}-g)^{\sigma}}e^{-\frac{c}{(g_{c}-g)^{\sigma}}}$ near
$g_{c}$. Fitting $\epsilon^{\prime}$ with Padé polynomials, we indeed found a
stable zero point. We have tried a number of different methods for unveiling
an exponential singularity masked by an analytic background, and in the end
this simple method worked the best. In appendix A we apply this method to an
explicitly known function and show that it works well.

The upper curve in figure 3 is the Padé fitting result for $N=9$. The
qualitative results for other $N>4$ cases are similar.

Figure 3: $\epsilon^{\prime}$ for $N=9$

The region with positive slope on the left hand side of $g_{c}$ should be
dominated by the singular structure. We fit this part of the curve with
$-\frac{A}{(g_{c}-g)^{\sigma}}e^{-\frac{c}{(g_{c}-g)^{\sigma}}}$ to extract
$g_{c}$ and $\sigma$. The lower curve in figure 3 is the fitting result for
$N=9$, and the numerical results are summarized in the table below (table 5):

N | $\sigma$ | $g_{c}$
---|---|---
5 | $0.21\pm 0.01$ | $1.1\pm 0.2$
6 | $0.29\pm 0.05$ | $0.96\pm 0.07$
7 | $0.31\pm 0.05$ | $0.83\pm 0.05$
8 | $0.40\pm 0.05$ | $0.68\pm 0.05$
9 | $0.5\pm 0.1$ | $0.57\pm 0.05$
10 | $0.5\pm 0.1$ | $0.48\pm 0.05$
20 | $0.5\pm 0.1$ | $0.136\pm 0.015$
Table 5: Estimations of $\sigma$ and $g_{c}$.

The error is obtained by changing the fitting region slightly or changing the
order of the Padé polynomials. There is a clear trend that $\sigma$ increases
from 0.2 to 0.5 as we dial up $N$. The results also show that $g_{c}<1$ for
$N>5$. According to the duality relation (8), there should be another
singularity $1/g_{c}$ with the same singular behavior. For $N=5$, our results
are not precise enough to tell whether $g_{c}<1$ or not. However, Padé fitting
to $\epsilon(g)$ and $\epsilon^{\prime}(g)$ both give two stable poles in the
$g>0$ region (appendix B), although they don’t obey the duality relation (8).
More sophisticated methods are required to find the precise location of
$g_{c}$ for $N=5$.

###  V.3 Evidence that $N\leq 4$ and $N>4$ are different

One may feel uncomfortable with our fitting method, because we manually
separate the cases $N\leq 4$ and $N>4$. In this subsection we present some
evidence that they really belong to two classes.

The first piece of evidence is the behavior of the fit to $\epsilon^{\prime}$
(figure 4,5). When $N>4$, it goes to 0 at $g_{c}$ to mimic exponential
suppression. When $N\leq 4$, it diverges because poles begin to accumulate in
the $g>g_{c}$ region, telling us that there is a branch cut.

Figure 4: $\epsilon^{\prime}$ for $N>4$ Figure 5: $\epsilon^{\prime}$ for
$N=3,4$

As a second test, we applied Padé fitting to $\epsilon^{\prime\prime}$, and
found a stable zero point for $N>5$ that is smaller than the zero point of
$\epsilon^{\prime}$ (figure 6). This is consistent with an exponential
singularity $e^{-c/(g_{c}-g)^{\sigma}}$, because as we take more derivatives
to the exponential form, smaller and smaller zeros will appear on the left
hand side of $g_{c}$. This will not happen for a singularity that goes like
$(g_{c}-g)^{-\sigma}$. Instead, poles and zeros will accumulate on the right
hand side of $g_{c}$, and this is exactly what happened when we fit
$\epsilon^{\prime\prime}$ for $N=3,4$. It is also these additional zeros that
make the Dlog Padé or inhomogeneous differential approximation to
$\epsilon^{\prime\prime}/\epsilon^{\prime}$ inaccurate, because it seems that
Padé approximants only work for $g$ smaller than the first zero point. For
$N=5$, however, there is no clear signature that $\epsilon^{\prime\prime}$ has
a smaller zero point than $\epsilon^{\prime}$.

Figure 6: The first zero point of $\epsilon^{\prime\prime}$ is smaller than
that of $\epsilon^{\prime}$ for N=9. The qualitative behaviors are the same
for $N>5$.

##  VI Summary

We calculated the ground state energy of the 1-dimensional N-state quantum
clock model up to order 18, and extracted its singular structure near the
critical point, for values of $N$ up to $20$. It was found that, for $N=3,4$,
there is a single critical point at $g_{c}=1$, and the exponent $\alpha$ for
the corresponding 2D classical model is $0.34\pm 0.01$ for $N=3$ while that
for $N=4$ is $-0.01\pm 0.01$. For $N>4$, There are two exponential
singularities related by $g_{c1}=1/g_{c2}$, and the ground state energy
behaves as $Ae^{-\frac{c}{|g_{c}-g|^{\sigma}}}+analytic\ terms$ near $g_{c}$.
The exponent $\sigma$ gradually grows from $0.2$ to $0.5$ as N increases from
5 to 9. These findings show that there exist a class of generalizations of KT
transition, and more insights can be obtained by studying models with
$N=5,6,7,8$. Better methods of extracting exponential singularities are also
needed to find the precise transition point for $N=5$, and to get a better
estimation of the exponents.

##  VII Acknowledgments

The author would like to thank Professor Tom Banks for countless discussions
throughout the research, and Professor Rajiv Singh, Professor Peter Young who
taught the author about the linked cluster expansion. This research was
supported by DOE under grant number DOE-SC0010008.

##  Appendix A Fitting the exact series of an exponential singularity

Here we repeat the calculation in section V.2, with the series of $\epsilon$
replaced by the series of $e^{-\frac{1}{(g_{c}-g)^{\sigma}}}$. The results are
listed below:

$g_{c}$ | $g_{cfit}$ | σ | $\sigma_{fit}$
---|---|---|---
1 | 1.0 | $0.5$ | 0.53
0.8 | 0.80 | $0.4$ | 0.38
0.6 | 0.59 | $0.3$ | 0.16

If we replace $\epsilon$ with $sin(g)+e^{-\frac{1}{(g_{c}-g)^{\sigma}}}$,
where $sin(g)$ represents an analytic background term, the results are:

$g_{c}$ | $g_{cfit}$ | σ | $\sigma_{fit}$
---|---|---|---
1 | 0.94 | $0.5$ | 0.43
0.9 | 0.89 | $0.4$ | 0.45
0.8 | 0.79 | $0.3$ | 0.18

We see that the fitting results for $g_{c}$ are always precise.
$|g_{c}-g_{cfit}|$ is controlled below $0.06$. The estimations of $\sigma$
when $\sigma\geq 0.4$ are also reasonable. $|\sigma-\sigma_{fit}|$ is always
smaller than $0.07$. When $\sigma=0.3$, the error can be as large as $0.14$.
But $\sigma_{fit}$ is still smaller than $0.5$, so it’s qualitatively correct.

##  Appendix B Stable real poles of $\epsilon(g)$ and $\epsilon^{\prime}(g)$
when $N=5$

Polynomial type | Real poles for $\epsilon(g)$
---|---
$[9/8]$ | $0.788095,1.24853,5.67655$
$[8/7]$ | $1.26307,5.14201$
$[7/6]$ | $1.21815,7.88399$
$[5/4]$ | $1.28659,6.82486$
Polynomial type | Real poles for $\epsilon^{\prime}(g)$
---|---
$[7/7]$ | $1.15988,2.88669$
$[6/6]$ | $1.0942,4.79821$
$[5/5]$ | $1.33875,3.8271$
$[4/4]$ | $1.16288,4.26156$

##  Appendix C The ground state energy density series

$N$ | $\epsilon(g)$
---|---
3 | $\begin{aligned} &-2-0.33333333333333326g^{2}-0.05555555555555558g^{3}\\\ &-0.015432098765432216g^{4}-0.010802469135802482g^{5}\\\ &-0.005596517299192159g^{6}-0.003382783789733934g^{7}\\\ &-0.0024418478191840687g^{8}-0.0017083823549243165g^{9}\\\ &-0.0012505362271225252g^{10}-0.0009640588459594025g^{11}\\\ &-0.0007532607066100003g^{12}-0.0006002324824848607g^{13}\\\ &-0.0004884680877595293g^{14}-0.00040306911349643267g^{15}\\\ &-0.0003367619172180523g^{16}-0.00028468719829159695g^{17}\\\ &-0.00024306955918608876g^{18}+O(g^{19})\end{aligned}$
$N$ | $\epsilon(g)$
---|---
4 | $\begin{aligned} &-2-0.5g^{2}-0.03125g^{4}-0.0078125g^{6}-0.0030517578125g^{8}\\\ &-0.001495361328125g^{10}-0.0008411407470703125g^{12}\\\ &-0.0005192756652832031g^{14}-0.00034280307590961456g^{16}\\\ &+O(g^{18})\end{aligned}$
5 | $\begin{aligned} &-2-0.7236067977499783g^{2}-0.01082711823295851g^{4}\\\ &-0.0050000000000000044g^{5}+0.012834208342438508g^{6}\\\ &-0.004476748935007664g^{7}+0.0071691845190831605g^{8}\\\ &-0.0014582789036703438g^{9}+0.00363340974879511g^{10}\\\ &+0.00042817768624983307g^{11}+0.0009825430279915533g^{12}\\\ &+0.0009009222496709941g^{13}+0.00027667263772020514g^{14}\\\ &+0.0009072543398714415g^{15}-0.00006787109149526856g^{16}\\\ &+0.00048470861631427255g^{17}+0.00004878354324601734g^{18}\\\ &+O(g^{19})\end{aligned}$
6 | $\begin{aligned} &-2-g^{2}+0.016666666666666607g^{4}+0.08043055555555534g^{6}\\\ &+0.05265773483846181g^{8}+0.03615288217802676g^{10}\\\ &+0.005796349140238799g^{12}-0.005592712308918113g^{14}\\\ &-0.04275193393460419g^{16}+O(g^{18})\end{aligned}$
7 | $\begin{aligned} &-2-1.3279852776056806g^{2}+0.09797290679170478g^{4}\\\ &+0.35397193583896414g^{6}-0.000637755102040817g^{7}\\\ &+0.3085285764405121g^{8}-0.0019474457234286945g^{9}\\\ &+0.2608242736968025g^{10}-0.0008936678382355442g^{11}\\\ &-0.27307294524474823g^{12}+0.006680757899727427g^{13}\\\ &-0.5706053033136786g^{14}+0.014034959344389308g^{15}\\\ &-3.1048948786406925g^{16}+0.030755900001374098g^{17}\\\ &-0.6577812813212631g^{18}+O(g^{19})\end{aligned}$
8 | $\begin{aligned} &-2-1.7071067811865461g^{2}+0.28545145311140274g^{4}\\\ &+1.2452271184234416g^{6}+1.4021698692988345g^{8}\\\ &+1.481704469767327g^{10}-6.297416226458864g^{12}\\\ &-13.136066464760518g^{14}-119.4409371149577g^{16}+O(g^{18})\end{aligned}$
9 | $\begin{aligned} &-2-2.1371580426032555g^{2}+0.6607776898982003g^{4}\\\ &+3.7994617012802543g^{6}+5.479144293201969g^{8}\\\ &-0.00009645061728395061g^{9}+7.090071901275373g^{10}\\\ &-0.0008103680532492554g^{11}-84.32489227044425g^{12}\\\ &-0.0008946489050342989g^{13}-200.28503141812962g^{14}\\\ &0.02226349726079538g^{15}-3201.6764082094887g^{16}\\\ &+0.08036690433538807g^{17}+6989.784090313808g^{18}+O(g^{19})\end{aligned}$
10 | $\begin{aligned} &-2-2.618033988749893g^{2}+1.3441206615821706g^{4}\\\ &+10.379000385996093g^{6}+18.939873150481205g^{8}\\\ &+29.18326653883338g^{10}-829.172485374158g^{12}\\\ &-2284.117236667422g^{14}-63633.110395201365g^{16}+O(g^{18})\end{aligned}$
20 | $\begin{aligned} &-2-10.215864547265355g^{2}+103.49335226791732g^{4}\\\ &+8906.588873287546g^{6}+103245.9724322232g^{8}\\\ &-212594.28296551108g^{10}-2820319368.8904266g^{12}\\\ &-23222204677.125977g^{14}-41202014867887.25g^{16}+O(g^{18})\end{aligned}$

## References

  * [1] E.Rabinovici, R. B. Pearson, and J. Shigemitsu. Phase structure of discrete Abelian spin and gauge systems. Physical Review D 19,3698(1979).
  * [2] M.B.Einhorn, R.Savit, and E.Rabinovici. A physical picture for the phase transitions in zn symmetric models.Nuclear Physics B 170,16(1980).
  * [3] C.J.Hamer and J.B.Kogut. Weak-coupling series and the critical indices of Z p spin systems in two dimensions. Physical Review B 22,3378 (1980).
  * [4] B.Nienhuis,Critical behavior of two-dimensional spin models and charge asymmetry in the Coulomb gas. Journal of Statistical Physics 34,731(1984).
  * [5] J.Frohlich, and T.Spencer. The Kosterlitz-Thouless transition in two-dimensional abelian spin systems and the Coulomb gas. Communications in Mathematical Physics 81,527(1981).
  * [6] J.Oitmaa,H.Chris, and W.Zheng. Series expansion methods for strongly interacting lattice models. Cambridge University Press, 2006.
  * [7] G.A.Baker and J.L.Gammel. The Padé approximant in theoretical physics. Academic Press, 1970.
  * [8] M.E.Fisher and H.A.Yang. Inhomogeneous differential approximants for power series. Journal of Physics A: Mathematical and General 12,1677(1979).
  * [9] I. G.Enting,Series analysis for the three-state Potts model. Journal of Physics A: Mathematical and General 13,L133(1980).
  * [10] O.Borisenko et al. Numerical study of the phase transitions in the two-dimensional Z (5) vector model. Physical Review E 83,041120(2011).
  * [11] S.K.Baek and M.Petter. Non-Kosterlitz-Thouless transitions for the q-state clock models. Physical Review E 82,031102(2010).
  * [12] M.Suzuki,Relationship between d-dimensional quantal spin systems and (d+ 1)-dimensional ising systems: Equivalence, critical exponents and systematic approximants of the partition function and spin correlations. Progress of theoretical physics 56,1454(1976).
  * [13] F.Y.Wu, The potts model. Reviews of modern physics 54,235(1982).
  * [14] D.D.Betts, The exact Solution of some Lattice Statistics Models with four States per Site. Canadian Journal of Physics 42,1564(1964).


# On the existence of $(r,g,\chi)$-cages ††thanks: Research supported by
PAPIIT-México IN108121, Intercambio Académico, UNAM. Grant: ”Buscando ciclos
largos en gráficas bipartitas” and CONACyT-México 282280.

Gabriela Araujo-Pardo
Instituto de Matematicas. Universidad Nacional Autónoma de México  México.
<EMAIL_ADDRESS>Zhanar Berikkyzy
Mathematics Department. Fairfield University
<EMAIL_ADDRESS>Linda Lesniak
Department of Mathematics. Western Michigan University
<EMAIL_ADDRESS>
###### Abstract

For integers $r\geq 2$ and $g\geq 3$, an _$(r,g)$ -graph_ is an $r$-regular
graph with girth $g$, and an _$(r,g)$ -cage_ is an $(r,g)$-graph of minimum
order. It is conjectured that all $(r,g)$-cages with even $g$ are bipartite,
that is, have chromatic number 2. Here we introduce the idea of an
$(r,g,\chi)$-graph, an $r$-regular graph with girth $g$ and chromatic number
$\chi$. We investigate the existence of such graphs and study in detail the
$(r,3,3)$-graphs of minimum order. We also consider $(r,g,\chi)$-graphs for
which there is a $\chi$-coloring where the color classes differ by at most 1.

##  1 Introduction

In this paper, we work with simple and finite graphs. We study a
generalization of the _Cage Problem_ , which has been widely studied since
cages were introduced by Tutte [9] in 1947 and after Erdös and Sachs [4]
proved their existence in 1963. An _$(r,g)$ -graph_ is an $r$-regular graph in
which the shortest cycle has length equal to $g$; that is, it is an
$r$-regular graph with girth $g$. An _$(r,g)$ -cage_ is an $(r,g)$-graph with
the smallest possible number of vertices among all $(r,g)$-graphs; the order
of an $(r,g)$-cage is denoted by $n(r,g)$. The Cage Problem consists of
finding $(r,g)$-cages; it is well-known that $(r,g)$-cages have been
determined only for very limited sets of parameter pairs $(r,g)$. There exists
a simple lower bound for $n(r,g)$, given by Moore (see [5]), and denoted by
$n_{0}(r,g)$. The cages that attain this bound are called _Moore cages_.

The existence of cages for all such integers $r,g$ has been proved, but very
few of these cages have been determined. However, based on these known cages,
an interesting conjecture has been made (this conjecture appears in [8], but
we can say that it is a _folklore Conjecture_ , because it is very well-known
among people interested on the Cage Problem).

######  Conjecture 1.1.

For even values of girth $g$, all $(r,g)$-cages are bipartite.

This conjecture naturally leads to a relationship between $(r,g)$-cages and
chromatic number since another way of stating this conjecture is the
following:

######  Conjecture 1.2.

(Conjecture 1.1)

For even values of girth $g$, all $(r,g)$-cages have chromatic number equal to
2.

Clearly, every $(r,g)$-cage with odd $g$ has chromatic number at least $3$.
Furthermore, for any $g\geq 3$, any $(r,g)$-graph, independent of whether it
is a cage or not, may have chromatic number at least $3$.

##  2 Definitions and background

The ideas expressed previously motivate the following definitions:

######  Definition 2.1.

An $(r,g,\chi)-\textbf{graph}$ is an $r\geq 2$-regular graph of fixed girth
$g\geq 3$ and chromatic number equal to $\chi\geq 2$.

######  Definition 2.2.

An $(r,g,\chi)-\textbf{cage}$ is an $(r,g,\chi)$-graph of minimum order, and
we denote by $n(r,g,\chi)$ the order of an $(r,g,\chi)$-cage.

The idea of this paper is the question of the existence of $(r,g,\chi)$-cages
for any $r\geq 2$, $g\geq 3$ and $\chi\geq 2$. Note that if $\chi=k$ this
implies that the graph is $k$-partite, but not $(k-1)$-partite so this problem
is equivalent to asking what is the smallest $k$-partite $r$-regular graph
with fixed girth $g$. Therefore we can give the following equivalent
definitions:

######  Definition 2.3.

An $(r,g,k)-\textbf{graph}$ is a $k$-partite (non $(k-1)$-partite) $r$-regular
graph, for $r\geq 2$ of fixed girth $g\geq 3$

######  Definition 2.4.

An $(r,g,k)-\textbf{cage}$ is an $(r,g,k)$-graph of minimum order, and we
denote by $n(r,g,k)$ the order of an $(r,g,k)$-cage.

We will consider the existence of $(r,g,k)$-cages, or equivalently, the
existence of $(r,g,\chi)$-cages. In our following work we will use the
terminology of $(r,g,\chi)$-cage.

By Brooks’ Theorem, $(r,g,\chi)$-graphs exist only if $\chi\leq r+1.$ The
authors of this paper do not know any result that proves the existence of
$(r,g,\chi)$-graphs for $4\leq\chi\leq r+1$. In Sections 3-5, we focus on the
problem for $\chi=3$.

In Section 3 we determine infinite classes of $(r,3,3)$-cages and we note that
in all $3$-colorings of these cages the size of the color classes differ by at
most one. This motivates the definition of $(r,g,\chi)$-equitable graph that
we study in Section 5.

In Section 4, assuming Conjecture 1.1, we establish the existence of
$(r,g,3)-$graphs for any $r\geq 2$, $g\geq 3$. Notice that, also by the
Conjecture 1.1, the $(r,g)$-cages for even $g\geq 4$, are $(r,g,2)$-cages.

In particular, by Brooks’ Theorem we know that every $(3,g)$-cage of odd girth
$g\geq 3$, except $K_{4}$, has chromatic number 3. Then the $(3,g)$-cages,
except $K_{4}$ which is a $(3,3,4)$-cage, are exactly the $(3,g,3)$-cages. In
this paper we are particularly interested in $(r,g,\chi)$-graphs of odd girth
$g$.

##  3 $(r,3,3)$-cages

In this section we focus on $(r,3,3)$-graphs and determine $n(r,3,3)$ for
$r\geq 2.$ Moreover, we describe an infinite class of $(r,3,3)$-cages for all
$r$ and, based on the parity of $r$, essentially determine all such cages.

In the last case in the proof of Theorem 3.2, we use the following result of
Moon and Moser [7].

######  Theorem 3.1.

If $G$ is a balanced bipartite graph with $2n$ vertices having minimum degree
$\delta(G)>n/2$, then $G$ is hamiltonian.

######  Theorem 3.2.

For $r\geq 2$ we have:

$n(r,3,3)=\left\\{\begin{array}[]{cr}r+r/2&\mbox{if $r$ is even;}\\\ r+\lceil
r/2\rceil+1&\mbox{if $r$ is odd, and $\lceil r/2\rceil$ is even;}\\\ r+\lceil
r/2\rceil+2&\mbox{if $r$ is odd, and $\lceil r/2\rceil$ is
odd.}\end{array}\right.$

###### Proof.

We first determine a lower bound on $n(r,3,3)$. Let $G$ be an $r$-regular
graph with $\chi(G)=3.$ Color $G$ with 3 colors, resulting in color classes
$A$, $B$ and $C,$ with $|A|\geq|B|\geq|C|.$ Since $G$ is $r$-regular,
$|A|+|B|\geq r,|B|+|C|\geq r$ and $|A|+|C|\geq r.$ Consequently
$2|A|+2|B|+2|C|\geq 3r,$ that is, $|V(G)|\geq\frac{3r}{2}$ and so $|V(G)|\geq
r+\lceil r/2\rceil.$

In the case $r$ is even, the $(r,3,3)$-graph $K_{r/2,r/2,r/2}$ attains this
bound and so $n(r,3,3)=r+r/2.$

In the case $r$ is odd and $\lceil r/2\rceil$ is even, it follows that
$r+\lceil r/2\rceil$ is odd and so no $r$\- regular graph of order $r+\lceil
r/2\rceil$ exists. Thus $n(r,3,3)\geq r+\lceil r/2\rceil+1.$ The graph
$G=K_{\lceil r/2\rceil,\lceil r/2\rceil,\lceil r/2\rceil}$ has order $r+\lceil
r/2\rceil+1$ which is even and is $(r+1)$ -regular. Removing any 1-factor from
$G$ results in an $r$-regular graph with girth 3 and chromatic number 3.
Therefore $n(r,3,3)=r+\lceil r/2\rceil+1.$

Finally, if $r$ is odd and $\lceil r/2\rceil$ is odd, it follows that
$r+\lceil r/2\rceil$ is even. Suppose that $|V(G)=r+\lceil r/2\rceil$, then it
follows that $|A|=|B|=\lceil r/2\rceil$ and $|C|=\lfloor r/2\rfloor.$ Notice
that every vertex in $A$ is adjacent to every vertex in $B\cup C$ and every
vertex in $B$ is adjacent to every vertex in $A\cup C.$ But then each vertex
in $C$ has degree $r+1$, which contradicts the assumption that $G$ is
$r$-regular. Thus, $|V(G)\leq r+\lceil r/2\rceil+1$, which is odd. Since $G$
is $r$-regular with odd $r$, $|V(G)|$ must be even and so $n(r,3,3)\geq
r+\lceil r/2\rceil+2$. We will construct an $(r,3,3)$ graph that attains this
bound. Consider the graph $G=K_{(r+3)/2,(r+1)/2,(r+1)/2}$, it has order
$r+\lceil r/2\rceil+2$, chromatic number 3, and girth 3. Define $A,B,C$ as
above, so that every vertex of $A$ has degree $r+1$ in $G$ and every vertex of
$B\cup C$ has degree $r+2$ in $G.$ Select $x\in A$, $y\in B$ and $z\in C.$ We
can remove any 1-factor from $G$, that contains none of the edges $xy,yz$ or
$xz$ to create a graph $H$ with girth 3 and chromatic number 3. Furthermore,
every vertex of $A$ has degree $r$ in $H$ and every vertex of $B\cup C$ has
degree $r+1$ in $H$. Moreover, the subgraph $F$ of $H$ induced by $B\cup C$ in
$H$ is a spanning subgraph of $K_{(r+1)/2,(r+1)/2}$ in which every vertex has
degree at least $(r-1)/2>(r+1)/4,$ provided $r>3.$ This is true since $\lceil
r/2\rceil$ is odd. In this case, $F$ is hamiltonian (see [7]) and so $F$ has a
1-factor that does not contain the edge $yz$. We can remove this 1-factor to
create an $r$-regular graph with girth 3 and chromatic number 3 of order
$r+\lceil r/2\rceil+2$. Therefore, $n(r,3,3)=r+\lceil r/2\rceil+2.$

(a) Case 1: $(4,3,3)$

(b) Case 2: $(3,3,3)$

(c) Case 3: $(5,3,3)$

Figure 1:  The cases of $(r,3,3)$-cages

∎

Figure 1 has examples of the three constructions in the proof of Theorem 3.2.

We note that this theorem essentially describes the $(r,3,3)$-cages in the
first two cases. Also, in each of the $3$-colorings described in the proof,
the sizes of the color classes differ by at most 1. In Section 5 such
colorings will be called equitable colorings.

##  4 Existence of $(r,g,3)$-graphs

In this section, we will prove, assuming Conjecture 1.1, that $(r,g,3)$-graphs
exist for all $r\geq 2$ and any girth $g\geq 3$.

######  Theorem 4.1.

The $(r,g,3)$-graphs exist for any $r\geq 2$ and $g\geq 3$.

###### Proof.

We will divide the proof into two cases depending on the parity of the girth.

  * •

Case 1: Suppose that girth $g\geq 3$ is odd. Clearly a $g$-cycle is a
$(2,g,3)$-graph, in fact, it is a $(2,g,3)$-cage and Brooks’ Theorem, together
with the existence of $(3,g)$-cages, implies the existence of
$(3,g,3)$-graphs, or $(3,g,3)$-cages, for odd $g\geq 3$. We now prove the
existence of $(r,g,3)$-graphs for $r\geq 4$ and $g\geq 3$ odd. Let $G$ be an
$(r,g+1)$-cage and, as $g$ is odd, by Conjecture 1.2, $G$ is a
$(r,g+1,2)$-cage.

Now we divide the proof in other two sub-cases, depending of the parity of
$r$:

    * –

Case (1a): Suppose that $r\geq 4$ is even. Let $x$ be a vertex in a $(g+1)$\-
cycle and let $N(x)=\\{x_{1},x_{2},\ldots,x_{r}\\}$, ordering these neighbours
with the property that, at least, $\\{x_{1},x,x_{2}\\}$ is in a $(g+1)$-cycle.
Let $H=G-x$; we construct a new graph $H^{\prime}$ with $V(H^{\prime})=V(H)$
and $E(H^{\prime})=E(H)\cup\\{x_{i},x_{i+1}\\}$ for odd $1\leq i\leq r-1$. As
$d_{G}(x_{i},x_{j})=2$, for any $1\leq\\{i,j\\}\leq r$ and $i\not=j$, and
$\\{x_{1},x,x_{2}\\}$ is in a $(g+1)$-cycle in $G$, the edge
$\\{x_{1}x_{2}\\}$ is in a $g$-cycle in $H^{\prime}$, and we obtain an
$(r,g)$-graph. As $g$ is odd, the chromatic number of $H^{\prime}$ is at least
$3$. To finish, we will give a $3$-coloring of $H^{\prime}$. As $G$ is
bipartite, if $f:V(G)\longrightarrow\\{0,1\\}$ is a $2$-coloring of $G$, it
follows that if $f(x)=0$ then $f(N(x))=1$. We give a $3$-coloring of
$H^{\prime}$ as $f^{\prime}(V(H^{\prime}))\longrightarrow\\{0,1,2\\}$ with
$f(x_{j})=2$ for all even $2\leq j\leq r$ and $f^{\prime}(z)=f(z)$ in any
other case.

    * –

Case (1b): Suppose that $r\geq 4$ is odd. Take an $xy$-edge, let
$N(x)-\\{y\\}=\\{x_{1},x_{2},\ldots,x_{r-1}\\}$ and
$N(y)-\\{x\\}=\\{y_{1},y_{2},\ldots,y_{r-1}\\}$, with the property that also
here $\\{x_{1},x,x_{2}\\}$ is in a $(g+1)$-cycle. As $r$ is odd, $r-1$ is
even; let $H=G-\\{x,y\\}$. Then $H^{\prime}$ a graph such that
$V(H^{\prime})=V(H)$ and
$E(H^{\prime})=E(H)\cup\\{x_{i}x_{i+1},y_{i}y_{i+1}\\}$, for odd $1\leq i\leq
r-2$. As in the previous case, the edge $\\{x_{1}x_{2}\\}$ is in a $g$-cycle
in $H^{\prime}$, and we obtain an $(r,g)$-graph. Also, as before, the
chromatic number of $H^{\prime\prime}$ is at least $3$ and we give a
$3$-coloring $f^{\prime}$ of $H^{\prime}$ taking into account the $2$-coloring
of $G$ as before. Here $f^{\prime}(V(H^{\prime}))\longrightarrow\\{0,1,2\\}$
with $f(\\{x_{j},y_{j}\\})=2$ for all even $2\leq j\leq r-1$ and
$f^{\prime}(z)=f(z)$ in any other case.

In both cases, we obtain an $(r,g,3)$-graph for odd $g\geq 3$.

  * •

Case 2: Suppose the girth $g\geq 4$ is even and let $G$ be an $(r,g)$-cage. By
Conjecture 1.2, $G$ is an $(r,g,2)$-cage. First, we will note that in $G$,
there is no edge $e$ that is in all the cycles of length $g$. To prove this
statement we will use the constructions given in Case 1. Suppose that the
statement is false and that all the $g$-cycles in $G$ contain $xy=e$. Here,
divide the proof into two cases as before, depending on the parity of $r$. As
we will use the previous constructions, we will give the proof without many
details. Suppose that $r$ is even. Delete the vertex $x$ and, as a
consequence, we also delete the edge $e=xy$. By hypothesis, the new graph has
girth at least $g+1$, all the vertices have degree $r$ except a set of them
(all of degree $r-1$ and mutually at distance $2$). We make the same
construction as in Case 1a and obtain a $r$-regular graph of girth $g$ of
order $n(r,g)-1$, which is a contradiction. In the other case, if $r$ is odd,
we delete the edge $e=xy$ and repeat the construction given in Case 1b. Since
we delete the edge $e$, none of the cycles in the new graph has length smaller
than $g+1$. Also, in this construction, we only add edges between vertices
that, in the original graph, were at distance two and that were not incident
with the edge $e$, that is all of the new cycles have length at least $g+1$.
Then, we obtain an $r$-regular graph of girth $g$ and order $n(r,g)-2$, which
also is a contradiction.

Consequently, given an edge $xy$ in $G$ contained in a cycle of length $g$
there exists at least one other cycle of length $g$ that does not contain
$xy$. Subdividing the edge $xy$ with a vertex $z$ of degree two, we obtain a
graph $H$, such that $V(H)=V(G)\cup\\{z\\}$ and $E(H)=E(G)\cup\\{xz,zy\\}$,
where $xyz$ is a $2$-path in $H$. As $xy$ was in a $g$-cycle in $G$, now the
$xzy$-path is in a $(g+1)$-cycle of odd length (because $g$ is even) in $H$.
Therefore, the chromatic number of $H$ is at least $3$ and if $G$ is colored
as before, the coloring of $H$ preserves all the colors of $G$ and adds a new
color in $z$. Notice also that, as there exists a $g$-cycle that does not
contain $xy$ the girth of the graph is still $g$. Here we also give two
different constructions depending of the parity of $r$.

    * –

Case (2a): If $r$ is even, we take $\frac{r}{2}$ copies of $H$ and we identify
all the vertices $z$ in each copy. All the vertices have degree $r$ and the
graph has girth $g$ because all of these graphs have $g$-cycles that do not
include the edge $xy$.

    * –

Case (2b): If $r$ is odd, first of all take a copy of $H$, called
$H^{\prime}$. Clearly, the chromatic number of $H$ is equal to three, and $H$
inherited the coloring of $G$ except for the new vertex $z$ that has color
$2$. Recoloring $H^{\prime}$ exchanging the chromatic classes of colors $0$
and $2$ of $H$ in $H^{\prime}$, that is, $H^{\prime}$ is coloring with colors
$1$ and $2$ in all the vertices, except one vertex, called $z^{\prime}$, that
receives the color $0$. Join these two graphs adding the edge $zz^{\prime}$.
Here all the vertices have degree $r$ except $z$ and $z^{\prime}$ that have
degree $3$. Take $\frac{r-3}{2}$ copies of $H$ and $H^{\prime}$ (preserving
their colorings) and identify them in $z$ and in $z^{\prime}$ respectively. In
this new graph called $H^{\prime\prime}$, all the vertices have degree $r$,
the degree of the vertices different than $z$ and $z^{\prime}$ is clearly $r$
because it does not change and the degree of $z$ (and $z^{\prime}$) is now
$r-3+3=r$.

In both cases, we obtain $(r,g,3)$-graphs, and we prove their existence.

∎

As a corollary of this theorem, we have that:

######  Corollary 4.1.

The $(r,g,3)$-cages exist for any $r\geq 2$ and $g\geq 3$.

##  5 Equitable colorings

######  Definition 5.1.

Let $G$ a graph and $\chi$ a vertex coloring of $G$. We say that $\chi$ is an
equitable coloring of $G$ is all the chromatic classes differ at most by one.

######  Definition 5.2.

An $(r,g,\chi)$\- graph $G$ is called an $(r,g,\chi)$-equitable graph if there
exits an $\chi$-equitable coloring of $G$. Moreover, $G$ is an
$(r,g,\chi)$-equitable cage if $G$ is an $(r,g,\chi)$-equitable graph of
minimum order.

######  Remark 5.1.

All the $(r,3,3)$-cages constructed in the proof of Theorem 3.2 are
$(r,3,3)$-equitable cages.

We next show, assuming Theorem 4.1, that $(r,g,3)$-equitable graphs exist for
all $r\geq 2$ and $g\geq 3.$

######  Theorem 5.1.

The $(r,g,3)$-equitable graphs exist for all $r\geq 2$ and $g\geq 3$.

###### Proof.

Let $G$ be an $(r,g,3)$-graph and consider a 3-coloring of $G$ with color
classes $C_{1},C_{2},C_{3}.$ Assume further that
$|C_{1}|=x,|C_{2}|=y,|C_{3}|=z.$

Construct a new graph $G^{*}$ consisting of three disjoint copies
$G_{1},G_{2},G_{3}$ of $G.$ Then $G^{*}$ is $r$-regular, $g(G^{*})=r,$ and
$\chi(G^{*})=3$. Let $C_{ij}$ denote the copy of $C_{i}$ in $G_{j}.$ We give
an equitable 3-coloring of $G^{*}$ as follows.

Define $C_{1}^{*}=C_{11}\cup C_{22}\cup C_{33},C_{2}^{*}=C_{21}\cup C_{32}\cup
C_{13},C_{3}^{*}=C_{31}\cup C_{12}\cup C_{23}.$ Then $|C_{i}^{*}|=x+y+z$ for
$i=1,2,3.$ Thus $C_{1}^{*},C_{2}^{*},C_{3}^{*}$ is an equitable 3-coloring of
$G^{*}$, and so $G^{*}$ is an equitable $(r,g,3)$-graph.

∎

As a corollary of this theorem, we also have that:

######  Corollary 5.1.

The $(r,g,3)$-equitable cages exist for all $r\geq 2$ and $g\geq 3.$

For all odd $g$ every $(3,g)$-cage is a $(3,g,3)$-cage, except $K_{4}$. The
question here is if they have equitable 3-colorings when $g\geq 5$.

We conjecture that the answer is “yes” and this is motivated by the fact that
many of the known cages, including the Petersen Graph or the $(3,5)$-cage, the
Mc Gee Graph or the $(3,7)$-cage, at least one of the eighteen $(3,9)$-cages
(see [2]) and the $(3,11)$-cage (see Figure 3) have equitable 3-colorings.

Recall that, by Conjecture 1.2 all $(r,g)$-cages of even $g$ are
$(r,g,2)$-cages; for this reason, in the following, we will continue working
only with cages of odd girth and we leave the study of $(r,g,\chi)$ with $g$
even as an open problem.

To continue, in the following section we will analyze the question about the
existence of $(r,g,\chi)$-cages with odd girth and $r\geq 4$. Moreover, we
will prove that for $r=4$, $g=5$ and $\chi=3$, the unique $(4,5)$-cage
Robertson graph, see Figure 6.1, is the $(4,5,3)$-cage of order 19, but it is
not a $(4,5,3)$-equitable cage. We will also exhibit a $(4,5,3)$-equitable
cage of order $20$, showing that the question about the minimum order of an
$(r,g,\chi)$-equitable graph (or the order of an $(r,g,\chi)$-equitable cage)
make sense in general.

Figure 2:  The McGee graph is a $(3,7)$-cage, but it is also a
$(3,7,3)$-equitable cage

Figure 3:  One of the eighteen $(3,9)$-cages and the unique $(3,11)$-cage are
also a $(3,9,3)$\- and $(3,11,3)$-equitable cages

##  6 $(r,g,\chi)$-graphs with odd girth and $r\geq 4$

As indicated in the previous section, here we will show that the Robertson
Graph, which is a $(4,5,3)$-cage, is not a $(4,5,3)$-equitable cage, that is,
it has no equitable 3-coloring.

######  Theorem 6.1.

The Robertson Graph is not a $(4,5,3)$-equitable cage.

###### Proof.

Figure 4: A 3-non equitable coloring for Robertson cage

Let $G$ be the Robertson Graph. In Figure 6.1 we see that there exists a
subgraph of the $G$ that consists of four $5$-cycles and two special vertices
marked in the picture. To make it easier to discuss, we will label these
$5$-cycles as $\mathcal{C}_{5}^{1}=(x_{1},\ldots,x_{5})$,
$\mathcal{C}_{5}^{2}=(x_{5},\ldots,x_{9})$,
$\mathcal{C}_{5}^{3}=(x_{9},\ldots,x_{13})$,
$\mathcal{C}_{5}^{4}=(x_{13},\ldots,x_{17})$, two special vertices
$X=\\{x_{18},x_{19}\\}$, and three vertices that are common in two cycles
$Y=\\{x_{5},x_{9},x_{13}\\}$.

It is known that $\chi(G)=3$. We also know that there exists a $3$-coloring of
Robertson graph with chromatic classes of sizes $\\{5,7,7\\}$ (see Figure
6.1). Notice also that this $3$-coloring is not equitable. If there exists an
equitable coloring for the Robertson Graph it must have chromatic classes of
sizes $\\{6,6,7\\}$.

We note that in any $3$-coloring of the Robertson Graph, there can be at most
two vertices of one chromatic class in each pentagon defined before and at
most one element of one chromatic class also in $X$.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$$x_{10}$$x_{11}$$x_{12}$$x_{13}$$x_{14}$$x_{15}$$x_{16}$$x_{17}$$x_{18}$$x_{19}$
Figure 5:  The $(4,5)$-Robertson cage

Suppose that there exists an equitable $3$-coloring of Robertson Graph, and
the chromatic classes of this coloring are given by the sets $\mathcal{R}$,
$\mathcal{B}$, $\mathcal{G}$ corresponding to colors $red$, $blue$, $green$,
and suppose wlog $|\mathcal{R}|\geq|\mathcal{B}|\geq|\mathcal{G}|$. Then we
have that $|\mathcal{R}|=7$, and $|\mathcal{B}|=|\mathcal{G}|=6$.

To start the proof, we will analyze the structure of $\mathcal{R}$, the
chromatic class of order seven. Recall that there can be at most two vertices
of $\mathcal{R}$ in any of the four given pentagons and at most one in $Y$.

We will give some observations that we will prove:

  * •

It is not possible that there are two red vertices in two different sets given
by $\mathcal{C}_{5}^{i}\setminus Y$, for $i\in\\{1,2,3,4\\}$.

Notice that if there exist two red vertices in $\mathcal{C}_{5}^{2}\setminus
Y$ they must be $\\{x_{6},x_{8}\\}$ and immediately no element of
$X=\\{x_{18},x_{19}\\}$ can be red. And similarly, if we have two red vertices
in $\mathcal{C}_{5}^{3}\setminus Y$ they are $\\{x_{10},x_{12}\\}$.

Suppose that we have two red vertices in $\mathcal{C}_{5}^{1}\setminus Y$ and
two red vertices in $\mathcal{C}_{5}^{2}\setminus Y$. In the latter, as
mentioned, the red vertices are $\\{x_{6},x_{8}\\}$. The red vertices in
$\mathcal{C}_{5}^{1}\setminus Y$ are either $\\{x_{1},x_{3}\\}$ or
$\\{x_{2},x_{4}\\}$ .

First, suppose that $\\{x_{1},x_{3}\\}$ are the red vertices in
$\mathcal{C}_{5}^{1}\setminus Y$. Then we have that:

$N(x_{1},x_{3},x_{6},x_{8})=\\{x_{2},x_{4},x_{5},x_{7},x_{9},x_{14},x_{15},x_{16},x_{17},x_{18},x_{19}\\}.$

Since the red chromatic class has order $7$ we must have four more red
vertices, but they can be neither in $\mathcal{C}_{5}^{4}\setminus Y$ nor in
$X$. So all of them must be in $\mathcal{C}_{5}^{3}$ and this is not possible.

Now, suppose that $\\{x_{2},x_{4}\\}\in\mathcal{C}_{5}^{1}\setminus Y$ are
red. We have that:

$N(x_{2},x_{4},x_{6},x_{8})=\\{x_{1},x_{3},x_{5},x_{7},x_{9},x_{10},x_{12},x_{14},x_{15},x_{16},x_{18},x_{19}\\}.$

Here, only $x_{11},x_{13}$ in $\mathcal{C}_{5}^{3}$ can be red. But
$x_{11}x_{17}\in E(G)$ and this implies that no vertex of
$\mathcal{C}_{5}^{4}$ other than $x_{13}$ can be red and no vertices in $X$
are red. But then there are fewer than 7 red vertices, a contradiction.

A similar analysis must be done if we have two red vertices in
$(\mathcal{C}_{5}^{1}\cup\mathcal{C}_{5}^{3})\setminus Y$,
$(\mathcal{C}_{5}^{2}\cup\mathcal{C}_{5}^{4})\setminus Y$ or
$(\mathcal{C}_{5}^{3}\cup\mathcal{C}_{5}^{4})\setminus Y$.

Then we only have two cases, where we have two red vertices in
$\mathcal{C}_{5}^{1}\setminus Y$ or two red vertices in
$\mathcal{C}_{5}^{4}\setminus Y$. First, if we assume two red vertices in
$\mathcal{C}_{5}^{4}\setminus Y$ then we have two red vertices in
$\mathcal{C}_{5}^{2}$ and one of them must be $x_{5}$. The vertex $x_{9}$
cannot be red, and we must have one other red vertex in $\mathcal{C}_{5}^{2}$
and also only one more in $\mathcal{C}_{5}^{3}$ and one in $X$ (see the left
side on Figure 6). For the other case, if we assume two red vertices in
$\mathcal{C}_{5}^{1}\setminus Y$, but only one vertex in $\mathcal{C}_{5}^{4}$
and it is different than $x_{13}$, then there must be three red vertices in
$(\mathcal{C}_{5}^{2}\cup\mathcal{C}_{5}^{3})$ and one of them is $x_{9}$.
Finally, there is one red vertex in $X$ (see figure right on Figure 6).

In the sequel, we will show that the colors of all the vertices in both cases
are completely determined. Moreover, we will divide these two cases so that in
the first $x_{5}\in\mathcal{R}$ and the rest is exactly the first case above
and the second is $x_{9}\in\mathcal{R}$ and the rest is also a consequence
(see Figure 6 to understand the colorings).

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$$x_{10}$$x_{11}$$x_{12}$$x_{13}$$x_{14}$$x_{15}$$x_{16}$$x_{17}$$x_{18}$$x_{19}$

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$$x_{10}$$x_{11}$$x_{12}$$x_{13}$$x_{14}$$x_{15}$$x_{16}$$x_{17}$$x_{18}$$x_{19}$

Figure 6:  Two different cases of a red chromatic class of size 7 in Robertson
cage

  * •

In the following we will determine the coloring divided into two cases, when
$x_{5}$ is red and when $x_{9}$ is red. Moreover in both of the cases, we will
prove that it is not possible that the two chromatic classes $\mathcal{B}$ and
$\mathcal{G}$ both have size $6$. In fact in both cases one of them has size
$5$ and the other $7$. We conclude that it is not possible to have an
equitable coloring of the Robertson Graph.

    * –

Suppose that $x_{5}$ is red and that $x_{3}$ is also red. Since
$N(x_{3},x_{5})=\\{x_{2},x_{4},x_{6},x_{7},x_{9},x_{17}\\}$, then the other
red vertex in $\mathcal{C}_{5}^{2}$ must be $x_{8}$, and

$N(x_{3},x_{5},x_{8})=\\{x_{2},x_{4},x_{6},x_{7},x_{9},x_{15},x_{17},x_{19}\\}.$

Since in $\mathcal{C}_{5}^{2}\setminus Y$ there must be two red vertices, the
unique options are $x_{14}$ and $x_{16}$, and in $X$ the vertex $x_{18}$ must
be red. In this case, we have that:

$N(x_{3},x_{5},x_{8},x_{14},x_{16},x_{18})=\\{x_{1},x_{2},x_{4},x_{6},x_{7},x_{9},x_{10},x_{11},x_{13},x_{15},x_{17},x_{19}\\}$

.

Finally, we have one red vertex in $\mathcal{C}_{5}^{3}\setminus Y$ and it
must be $x_{12}$, and we finish the description of the red vertices in the
coloring (see Figure 6, left side).

Now suppose that $x_{5}$ is red, but in this case $x_{2}$ is the other red
vertex. Then
$N(x_{2},x_{5})=\\{x_{1},x_{3},x_{4},x_{6},x_{9},x_{10},x_{14}\\}$. There must
be two red vertices in $\mathcal{C}_{5}^{4}\setminus Y$ and these must be
$\\{x_{15},x_{17}\\}$. Since

$N(x_{2},x_{5},x_{15},x_{17})=\\{x_{1},x_{3},x_{4},x_{6},x_{8},x_{9},x_{10},x_{13},x_{14},x_{16},x_{18}\\},$

then the vertex $x_{7}$ in $\mathcal{C}_{5}^{2}\setminus Y$ must be red. But
then we cannot have a red $x_{11}$. However, if $x_{12}$ is red, then we have
a problem because $x_{12}x_{19}\in E(G)$ and no vertex of $X$ can be red.
Consequently, this case does not have a solution, that is, a chromatic class
of size $7$ with $\\{x_{2},x_{5}\\}$ colored red does not exist.

A similar analysis can be done if we assume $x_{13}$ instead of $x_{5}$ is red
and another vertex in $\mathcal{C}_{5}^{4}$, and two different vertices in
$\mathcal{C}_{5}^{1}\setminus Y$.

To finalize this case notice that between any two red vertices on the
hamiltonian cycle $C:x_{1},x_{2},...,x_{19},x_{1}$, we have vertices of
different chromatic classes and the number of vertices in each gap between any
pair of red vertices are $\\{1,2,3,1,1,1,3\\}$ if we start after $x_{3}$ in
the counter-clock direction. So if we want a coloring with two chromatic
classes of size $6$, it is necessary that if the colors are balanced in the
spaces with one vertex (2 green and 2 blue), one of the spaces with three
vertices, has two blue vertices and one green vertex and the other has two
green vertices and one blue. If $x_{4}$ is blue, then $x_{5}$ is green. If
$x_{13}\in\mathcal{B}$ then $x_{17}\in\mathcal{G}$. Moreover if
$x_{7}\in\mathcal{B}$ then $x_{6}\in\mathcal{G}$ and $x_{11}\in\mathcal{G}$,
and also $x_{9}\in\mathcal{G}$ and $x_{10}\in\mathcal{B}$, but $x_{2}$ should
be also green and also $x_{19}$ and $x_{1}$ is blue (see Figure 7 left side)
Then the green chromatic class has size $7$ and the blue chromatic class has
size $5$, and there does not exist a balanced coloring of the Robertson Graph
with these characteristics in the red chromatic class.

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$$x_{10}$$x_{11}$$x_{12}$$x_{13}$$x_{14}$$x_{15}$$x_{16}$$x_{17}$$x_{18}$$x_{19}$

$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$$x_{7}$$x_{8}$$x_{9}$$x_{10}$$x_{11}$$x_{12}$$x_{13}$$x_{14}$$x_{15}$$x_{16}$$x_{17}$$x_{18}$$x_{19}$

Figure 7:  Two different cases of a 3-non equitable coloring of Robertson cage

    * –

Suppose that $x_{9}$ is red, and there is one other red vertex in
$\mathcal{C}_{5}^{2}$. In this first case we assume $x_{7}$ is also red so
that the unique possible red vertex in $\mathcal{C}_{5}^{3}$ is $x_{12}$, and
we have the following
$N(x_{7},x_{9},x_{12})=\\{x_{3},x_{4},x_{5},x_{6},x_{8},x_{10},x_{11},x_{13},x_{19}\\}$.
As an immediate conclusion, $x_{18}$ must be a red vertex in $X$ and we must
have two red vertices in $\mathcal{C}_{5}^{4}\setminus Y$, and the options are
only $x_{14}$ and $x_{16}$, because $x_{17}\in N(x_{18})$. Then,at this point,
we have:

$N(x_{7},x_{9},x_{12},x_{14},x_{16},x_{18})=\\{x_{1},x_{2},x_{3},x_{4},x_{5},x_{6},x_{8},x_{10},x_{11},x_{13},x_{15},x_{17},x_{19}\\}$

and there can be no red vertex in $\mathcal{C}_{5}^{1}\setminus Y$ and this
case does not have solution.

The second case is, assuming $x_{9}$ is red, that $x_{6}$ is the other red
vertex in $\mathcal{C}_{5}^{2}$. As, $x_{6}x_{18}\in E(G)$ then $x_{19}\in
X\cap\mathcal{R}$ and
$N(x_{6},x_{9},x_{19})=\\{x_{1},x_{5},x_{7},x_{8},x_{10},x_{12},x_{13},x_{14},x_{18}\\}$.
Then, the other red vertex in $\mathcal{C}_{5}^{3}$ only can be $x_{11}$, and
the two red vertices in $\mathcal{C}_{5}^{4}\setminus Y$ are $x_{15}$ and
$x_{17}$. Then:

$N(x_{6},x_{9}x_{11},x_{15},x_{17},x_{19})=\\{x_{1},x_{3},x_{4},x_{5},x_{7},x_{8},x_{10},x_{12},x_{13},x_{14},x_{16},x_{18}\\}.$

Consequently, the red vertex in $\mathcal{C}_{5}^{1}$ must be $x_{2}$ and
everything is determined (see Figure 7 right side). A similar analysis can be
done if we begin with $x_{9}$ as red, consider firstly the second red vertex
in $\mathcal{C}_{5}^{3}$ instead of starting with $\mathcal{C}_{5}^{3}$, then
we have two options and only one will be possible.

To finalize we will prove, as in the previous case, that it will be impossible
to find an equitable coloring with this distribution of the red chromatic
class in $G$. Here the number of vertices in each gap between any pair of red
vertices are $\\{1,3,2,1,3,1,1\\}$ starting in $x_{1}$ in the counter-clock
direction (the same as in the previous case) and also here if we want a
coloring with two chromatic classes of length $6$ it is necessary that if we
balanced the colors in the spaces with one vertex (2 green and 2 blue), one of
the spaces with three vertices, has two blue vertices and one green vertex and
the other should have two green vertices and one blue. Here, if
$x_{1}\in\mathcal{B}$, then $\\{x_{5},x_{7}\\}\in\mathcal{G}$ and
$x_{4}\in\mathcal{B}$ and $x_{3}\in\mathcal{G}$. Immediately
$\\{x_{12},x_{14}\\}\in\mathcal{G}$ and $x_{15}\in\mathcal{B}$. But, as
$x_{10}x_{18}\in E(G)$ and both are vertices between red vertices, one of them
is blue and the other green (w.l.o.g. $x_{10}\in\mathcal{B}$ and
$x_{18}\in\mathcal{G}$). Finally, $x_{7}\in\mathcal{B}$ and
$x_{8}\in\mathcal{G}$ (see Figure 7, right side).

Then, newly the green chromatic class has size also $7$ and the blue chromatic
class has size $5$, and neither in this case, does not there exist a balanced
coloring of Robertson Graph.

∎

On Figure 8 is a $(4,5,3)$-equitable graph of order $20$ and three chromatic
classes of size $6$, $7$ and $7$. As the $(4,5,3)$-cage graph (the Robertson
graph) is not equitable, then $G$ is a $(4,5,3)$-equitable cage.

Figure 8:  The $(4,5,3)$-equitable cage

##  7 Future work.

Obviously, natural future research is working with regular graphs of odd girth
and a chromatic number greater or equal to $4$, because in this paper we only
worked with graphs of chromatic number equal to $3$.

For example, for girth $5$ the first cage that has chromatic number equal to
$4$ is the $(5,5)$-cage which has order $30$. Obviously, it is a
$(5,5,4)$-cage, but we do not know if it is equitable or not. Moreover, there
exist a lot of nice questions about the chromatic number of the cages, that
is, about the chromatic number of the minimum $(k;g)$-graphs known until this
moment (for any $k\geq 3$ and odd $g$).

On the other hand, when $g$ is even and $\chi\not=2$, the problem of finding
$(r,g,\chi)$-graphs, or $(r,g,\chi)$-cages, is naturally related to the
problem of finding cages with given girth pair. These graphs were introduced
in [6] and studied, for example in [1, 3]. The $(r;g,h)$-cages are $r$-regular
graphs of minimum order and fixed girth $g$, where $h$ is the length of the
smallest cycle of different parity of $g$ and $g<h$. Obviously, if $g$ is
even, an $(r;g,h)$-graph $G$ (in this context) could be an $(r,g,3)$-graph (in
our context), if the chromatic number of $G$ is $3$. For us, a natural future
research question is to study the relationship between these two “kinds” of
cages.

## References

  * [1] Balbuena C. and Salas J., On the order of graphs with a given girth pair. _Discrete Math._ 321, (2014), 68–75
  * [2] Brinkmann G., McKay B. and Saager C., The smallest cubic graphs of girth $9$. _Combinatorics, Probability and Computing_ 4, Issue 4, (1995), 317–329.
  * [3] Campbell C. M., On cages for girth pair $(6,b)$, _Discrete Math._ 177, (1997), 259–266.
  * [4] Erdös P. and Sachs. H., Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl. _Wiss. Z. Uni. Halle (Math. Nat.)_ , 12,(1963), 251–257.
  * [5] G. Exoo, R. Jajcay. Dynamic Cage Survey. _Electron. J. Combin_ , Dynamic Survey #DS16: Jul 26, (2013).
  * [6] Harary, F., Kovács P., Regular graphs with given girth pair. _J.Graph Theory_ , 7, (1983), 209-218.
  * [7] J. Moon and L. Moser. On hamiltonian bipartite graphs. _Israel J. Math._ , 1, (1963), 163-165.
  * [8] T. Pisanski M. Boben, D. Maruŝiĉ, A. Orbanić, A. Graovac. The 10-cages and derived configurations. _Disc. Math._ , 275, No.1-3, (2004), 265–276.
  * [9] Tutte. W.T., A family of cubical graphs. _Math. Proc. Cambridge Philos. Soc._ , 43 (4), (1947), 459-474.