# On Mixed Cages of Girth 6

Gabriela Araujo-Pardo  Instituto de Matemáticas, Universidad Nacional Autónoma
de México, Campus Juriquilla, Querétaro, Mexico  Lydia Mirabel Mendoza-Cadena
MTA-ELTE Matroid Optimization Research Group, Department of Operations
Research, ELTE Eötvös Loránd University, Budapest, Hungary.

###### Abstract

A $[z,r;g]$-mixed cage is a mixed graph of minimum order such that each vertex
has $z$ in-arcs, $z$ out-arcs, $r$ edges, and it has girth $g$. We present an
infinite family of mixed graphs with girth 6. This construction also provides
an upper bound on the minimum order of mixed cages of girth 6. Additionally,
we introduce a lower bound on the minimum order for any mixed cage.

Keywords: mixed cages; girth; biaffine plane; projective plane; order bounds

##  1 Introduction

Mixed regular cages where introduced by Araujo-Pardo, Hernández-Cruz, and
Montellano-Ballesteros [1].

A _mixed graph_ is a simple111No parallel arcs or edges are allowed, neither a
parallel arc and edge. graph $G=(V;E\cup A)$ where $V(G)$ is the set of
vertices, $E(G)$ is the set of edges and $A(G)$ the set of arcs. We denote an
edge between $u$ and $v$ by $uv$ and an arc from $u$ to $v$ by $(u,v)$. We say
that $u$ and $v$ are _edge-adjacent_ (_arc-adjacent_) if they are connected by
an edge (arc).

Walks, paths and cycles are referred by a sequence of vertices
$(v_{0},v_{1},\dots,v_{n})$, where $v_{i}$ and $v_{i+1}$ are connected by
either the arc $(v_{i},v_{i+1})$ or by the edge $v_{i}v_{i+1}$. The _girth_ of
$G$ is the length of the shortest cycle.

If each vertex has $z$ in-arcs, $z$ out-arcs, and $r$ edges, then the graph is
called _mixed regular graph_. If, additionally, it has girth $g$, then we say
that $G$ is a _$[z,r;g]$ -mixed graph_.

A _$[z,r;g]$ -mixed cage_ is a $[z,r;g]$-mixed graph of minimum order, where
the _order_ of a graph is the number of vertices. The minimum order of
$[z,r;g]$-mixed graphs is denoted by $n[z,r;g]$.

#### Previous work.

As mentioned above, in [1] it is described the notion of mixed regular graphs
for the first time. Explicit mixed cages for given values and some lower
bounds were presented. Additionally, they gave a lower bound on the order of
$[1,r;g]$-mixed cages, also known as the AHM bound. This bound relies on the
Moore’s lower bound (see e.g. [2]). The authors [1] also showed that the AHM
bound is achieved for $r=2$ and any $g$. Exoo [3] showed that the AHM bound
can be achieved for $r=3$ and $g=5,6$.

Later, Araujo-Pardo, De la Cruz, and González-Moreno [4] showed that the order
of a $[z,r;g]$-mixed cage is a monotone function with respect to $g$ if
$z\in\\{1,2\\}$. Moreover, they proved that such $[z,r;g]$-mixed cages are
2-connected, and for general $z$ the graphs are strongly connected. Further
constructions and lower bounds were presented for $g=5$ too. This later uses
incidence structures, in particular, the elliptic semiplane of type $C$. Next
section includes more details on this topic.

Exoo [3] focused on $z\in\\{1,2\\}$ and presented a series of mixed cages and
upper bounds for different values of $r\leq 5$ and $g\leq 8$, by the use of
computer searches.

#### Our results.

In Section 3, we present a construction of the $[1,3;6]$-mixed cage from the
projective plane on the Galois field of order 4. Later in Section 4, we define
an infinite family of mixed graphs of girth 6 using the incidence graph of the
biaffine plane over the field $\mathbb{Z}_{q}$ with $q$ a prime. This
construction provides upper bounds for the minimum order of mixed graphs of
girth 6. Finally, in Section 5 we provide a lower bound for the minimum order
of $[z,r;g]$-mixed cages for any values of $z,r,$ and $g$.

##  2 Preliminaries

To be self-contained, we describe in detail three graphs that are obtained
from projective planes of order $q$. Constructions using the incidence graph
of a projective plane or their substructures have been widely used. The first
construction was presented by Miller and Sirán [5], followed by Hafner [6],
Araujo-Pardo, Noy and Serra [7], and Araujo-Pardo, Balbuena, Miller and
Ždímalová [8], just to mention some examples. Regarding mixed cages, Araujo-
Pardo, De la Cruz, and González-Moreno [4] generated a family of
$[z,r;5]$-mixed graphs using this technique.

#### The graph $\bm{G_{(2,q)}}$ of the projective plane on the Galois field.

Let $q$ be a prime power, and let $\mathbb{G}_{q}$ be the Galois field of
order $q$. We describe the projective plane $PG(2;q)$. Let $L_{\infty}$ and
$P_{\infty}$ be the incident line and point in the projective plane, called
the infinity line and infinity point, respectively. The classes of lines
(points) are denoted by $L_{i}$ ($P_{i}$) for $i\in\mathbb{G}_{q}$. Each line
$L$ have $q+1$ points and each point $P$ is incident to $q+1$ lines. Any line
in $L_{m}$ described by $y=mx+b$ is denoted by $[m,b]$, and any point in
$P_{x}$ is denoted by $(x,y)$. For each $i\in\mathbb{G}_{q}$, the set of
points incident to $L_{i}$ is $\\{(i,j)\,\,|\,\,j\in\mathbb{G}_{q}\\}$ and the
set of lines incident to $P_{i}$ is $\\{[i,j]\,|\,j\in\mathbb{G}_{q}\\}$.
Finally, for $m,b\in\mathbb{G}_{q}$ the line $[m,b]$ is incident to all points
$(x,y)$ such that $y=mx+b$ holds for $x,y\in\mathbb{G}_{q}$.

The projective plane $PG(2;q)$ has an incidence graph associated that we
denote by $G_{(2,q)}$. Each line and point has a unique associated vertex
$v\in V(G_{(2,q)})$. Similarly, $uv\in E(G_{(2,q)})$ if and only if their
associated line and point are incident in $PG(2;q)$. For an easy reading, we
may refer to “line $[m,b]$” (point $(x,y)$) instead of “vertex associated to
the line $[m,b]$” (point $(x,y)$). Note that $G_{(2,q)}$ has order
$2q^{2}+2q+2$, diameter 3 and girth 6. In fact, it is known that this
incidence graph is a $[0,q;6]$-mixed cage (undirected cage) that attains the
Moore bound.

#### The bipartite graph $\bm{B_{q}}$.

The corresponding plane of the following incidence graph is also known as the
biaffine plane. Consider the graph $G_{(2,q)}$ constructed above and delete
the vertices $L_{\infty},P_{\infty},$ and $L_{i},P_{i}$ for
$i\in\mathbb{G}_{q}$. We are left with a bipartite graph that we denote by
$B_{q}$. Note that $B_{q}$ consists only on points $(x,y)$ and lines $[m,b]$,
for $x,y,m,b\in\mathbb{G}_{q}$, and it has order $2q^{2}$, diameter 4 and
girth 6 if $q\geq 3$, and girth 8 if $q=2$.

#### The circulant digraph
$\overset{\bm{\rightarrow}}{\bm{C}}_{\bm{q}}\bm{{(i_{1},\dots,i_{k})}}$.

Consider the field $\mathbb{Z}_{q}$ and $i_{1},\dots,i_{k}\in\mathbb{Z}_{q}$.
A _circulant digraph_ $\overset{\rightarrow}{C}_{q}(i_{1},\dots,i_{k})$ has a
vertex $v_{i}$ for each $i\in\\{0,1,\dots,q-1\\}$. There exists an arc
$(v_{a},v_{b})$ if and only if $b\equiv a+i\mod q$ for some $i\in
i_{1},\dots,i_{k}$. It is known that if $q=z(g-1)+1$, then
$\overset{\rightarrow}{C}_{q}(1,2,\dots,z)$ is a $[z,0;g]$-mixed graph (see
e.g. [9, 10]).

The following conjecture is derived from the known upper bound on the order of
circulant digraphs of the form $\overset{\rightarrow}{C}_{q}(1,2,\dots,z)$.

######  Conjecture 1 (Behzad-Chartrand-Wall, [9]).

Let $n[z,g]$ denote the minimum order of a $z$-regular digraph of girth $g$.
Then, $n[z,g]=z(g-1)+1$.

The conjecture has been shown true for $r=2,3,4$ and for vertex-transitive
digraphs (see e.g. [10]).

#### The tree $\bm{\mathcal{T}_{r,g}}$ and lower Bounds for mixed cages.

Araujo-Pardo, Hernández-Cruz, and Montellano-Ballesteros [1] provided a very
simple lower bound for the minimum order of $[1,r;g]$-mixed cages which is
based on Moore’s bound $n_{0}[r,g]$ that it is defined as:

$\displaystyle n_{0}[r,g]=\begin{cases}\displaystyle
1+r\sum_{i=1}^{k-1}(r-1)^{i}&\text{ if the girth is $g=2k+1$},\\\\[10.00002pt]
\displaystyle 2\sum_{i=0}^{k-1}(r-1)^{i}&\text{ if the girth is $g=2k$}.\\\
\end{cases}$

Surprisingly, the bound for $n[1,r;g]$ turn out to be a very good lower bound
as Exoo [3] exhibited in his work, as mentioned in Section 1. This bound is
obtained by counting the vertices of the mixed-tree $\mathcal{T}_{r,g}$. This
tree has $g$ nodes at level 0, which we denote by $v_{1},\dots,v_{g}$. For
each node $v_{i}=v_{2},\dots,v_{g-1}$, we add $r$ children
$u_{i,1},\dots,u_{i,r}$. We add $r-1$ children $w_{i,j,1},\dots,w_{i,j,r-1}$
to each child $u_{i,j}$ of vertices $v_{3},\dots,v_{g-2}$. If $g$ is odd, we
also add $r-1$ children to
$w_{\frac{g-1}{2},j,1},\dots,w_{\frac{g-1}{2},j,r-1}$ for all $j$. Finally, we
direct the path from $v_{1}$ to $v_{g}$ of $\mathcal{T}_{r,g}$. That is,
$\mathcal{T}_{r,g}$ has a directed path $(v_{1},\dots,v_{g})$ and it attaches
a Moore tree of depth $i$ to vertices $v_{i+1}$ and $v_{g-i}$ for
$i=1,\dots,\lfloor\frac{g-1}{2}\rfloor$.

######  Theorem 2 (AHM lower bound,[1]).

Let $n[1,r;g]$ be the order of a $[1,r;g]$-mixed cage. Then,

$\displaystyle n[1,r;g]\geq n_{\text{AHM}}[1,r;g]=\begin{cases}\displaystyle
2\left(1+\sum_{i=1}^{k-1}n_{0}[r,2i+1]\right)+n_{0}[r,g]&\text{ if the girth
is $g=2k+1$},\\\\[15.00002pt] \displaystyle
2\left(1+\sum_{i=1}^{k-1}n_{0}[r,2i+1]\right)&\text{ if the girth is
$g=2k$}.\\\ \end{cases}$ (1)

##  3 The [1,3;6]-mixed cage from Galois’ Projective Plane

In this section, we derive the $[1,3;6]$-mixed cage starting from the graph
$G_{(2,4)}$ described in Section 2. Recall that $G_{(2,4)}$ represents the
adjacency graph of the Galois projective plane $GF(2,4)$ and it contains 42
nodes. Exoo [3] exhibited a $[1,3;6]$-mixed cage with 30 nodes that can be
seeing as the connection of tree directed cycles with 10 vertices. The mixed
cycles generated the girth equals to 6. It is not difficult to see that our
construction is equivalent to that graph.

######  Theorem 3.

The $[1,3;6]$-mixed cage can be derived from $G_{(2,4)}$.

###### Proof.

Recall that $G_{(2,4)}$ has girth 6. Consider the following construction,
where the main idea is to keep the girth while adding the missing arcs and
trying to keep as many edges from $G_{(2,4)}$ as possible. Clearly, we need to
remove 12 vertices too. Figure 1 shows the final graph. We refer as _direct
edge $\overrightarrow{uv\,\,}$_ to the operation of deleting edge $uv$ and
then adding arc $(u,v)$. Hence, the construction has the following steps.

  1. 1.

Erase lines $[m,0],[m,1]$ for $m\in\\{0,1\\}$, and
$[\alpha,\alpha],[\alpha,\alpha^{2}]$.
Erase points $(x,0),(x,1)$ for $x\in\\{1,\alpha\\}$, and
$(\alpha^{2},\alpha),(\alpha^{2},\alpha^{2})$.

  2. 2.

Direct edges
$\overrightarrow{[\alpha^{2}\alpha]P_{\alpha^{2}}},\,\,\overrightarrow{P_{\alpha^{2}}L_{\infty}},\,\,\overrightarrow{L_{\infty}P_{\infty}},\,\,\overrightarrow{P_{\infty}L_{0}},\,\,\overrightarrow{L_{0}(0,\alpha^{2})\,\,}$.

  3. 3.

Add arcs $(P_{0},L_{\alpha^{2}})$, and $(P_{1},L_{\alpha})$.
Add arc $(P_{\alpha},L_{1})$ and orient edges
$\overrightarrow{{[\alpha,0]}{(1,\alpha)}\,\,}$ and
$\overrightarrow{[\alpha,1](1,\alpha^{2})\,\,}$.

  4. 4.

Add arc $\displaystyle\left(L_{1},(0,\alpha)\right)$ and orient edges
$\overrightarrow{(1,\alpha)[0,\alpha]\,\,}$ and
$\overrightarrow{(1,\alpha^{2})[1,\alpha]\,\,}$.
Add arc $\displaystyle\left(L_{\alpha},(0,1)\right)$ and orient edge
$\overrightarrow{(\alpha,\alpha)[\alpha,1]\,\,}$.
Add arc $\displaystyle\left(L_{\alpha}^{2},(0,0)\right)$ and orient edge
$\overrightarrow{(\alpha^{2},1)[\alpha,0]\,\,}$.

  5. 5.

Add arcs
$\displaystyle\left([\alpha^{2},0],P_{1}\right),\left([\alpha^{2},1],P_{0}\right),\left([\alpha^{2},\alpha^{2}],P_{\alpha}\right)$.

  6. 6.

Add arc $\displaystyle\left([0,\alpha],(\alpha^{2},0)\right)$, orient edge
$\overrightarrow{(0,\alpha)[\alpha^{2},\alpha]\,\,}$ and remove edge
$(\alpha^{2},0)[1,\alpha^{2}]$.
Add arc $\displaystyle\left([0,\alpha^{2}],(\alpha^{2},1)\right)$, orient edge
$\overrightarrow{(0,\alpha^{2})[\alpha^{2},\alpha^{2}]\,\,}$ and remove edge
$(\alpha,\alpha^{2})[0,\alpha^{2}]$.

  7. 7.

Add arcs $\displaystyle\left([1,\alpha],(\alpha,\alpha^{2})\right)$ and
$\displaystyle\left([1,\alpha^{2}],(\alpha,\alpha)\right)$.

  8. 8.

Add arcs $\displaystyle\left((0,1),[0,\alpha^{2}]\right)$,
$\displaystyle\left((0,0),[1,\alpha^{2}]\right)$,
$\displaystyle\left((\alpha^{2},0),[\alpha^{2},0]\right)$,
$\displaystyle\left((\alpha,\alpha^{2}),[\alpha^{2},1]\right)$.

  9. 9.

Add edge $[\alpha^{2},\alpha](0,\alpha^{2})$.

$P_{0}$$P_{1}$$P_{\alpha}$$P_{\alpha^{2}}$$L_{0}$$L_{1}$$L_{\alpha}$$L_{\alpha^{2}}$${[0,\\!1]}$${[0,\\!0]}$${[0,\\!\alpha]}$${[0,\\!\alpha^{2}]}$${[1\\!,\\!1]}$${[1\\!,\\!0]}$${[1\\!,\\!\alpha]}$${[1\\!,\\!\alpha^{2}]}$${[\alpha\\!,\\!1]}$${[\alpha\\!,\\!0]}$${[\alpha\\!,\\!\alpha]}$${[\alpha\\!,\\!\alpha^{2}]}$${[\alpha^{2}\\!,\\!1]}$${[\alpha^{2}\\!,\\!0]}$${[\alpha^{2}\\!,\\!\alpha]}$${[\alpha^{2}\\!,\\!\alpha^{2}]}$${(0,\\!1)}$${(0,\\!0)}$${(0,\\!\alpha)}$${(0,\\!\alpha^{2})}$${(1,1)}$${(1,0)}$${(1\\!,\\!\alpha)}$${(1\\!,\\!\alpha^{2})}$${(\alpha\\!,\\!1)}$${(\alpha\\!,\\!0)}$${(\alpha\\!,\\!\alpha)}$${(\alpha\\!,\\!\alpha^{2})}$${(\alpha^{2}\\!,\\!1)}$${(\alpha^{2}\\!,\\!0)}$${(\alpha^{2}\\!,\\!\alpha)}$${(\alpha^{2}\\!,\\!\alpha^{2})}$$P_{\infty}$$L_{\infty}$
Figure 1: [1,3;6]-mixed cage from graph $G_{(2,4)}$. Erased edges and vertices
are denoted by gray. Arcs are shown in blue. The new edge is shown in yellow.
The rest of edges belong to the original graph $G_{(2,4)}$, where line $[m,b]$
colors points $(x_{1},y_{1})$ and $(x_{2},y_{2})$, and thus each point has two
colors associated.

This graph has 30 vertices, and each one has three edges and one in- and one
out-arc. We verify no cycle of length less than 6 is created in any of the
steps.

Clearly, no new cycle is created in steps 1 and 2. For step 3, orienting edge
$\overrightarrow{{[\alpha,0]}{(1,\alpha)}}$ removes cycle
$(P_{\alpha},L_{1},(1,\alpha),[\alpha,0])$, and orienting edge
$\overrightarrow{[\alpha,1](1,\alpha^{2})}$ removes cycle
$(P_{\alpha},L_{1},(1,\alpha^{2})),[\alpha,1])$. Note that those mixed cycles
have the new arc and three edges from $G_{(2,4)}$, hence removing or correctly
directing an edge results in removing the mixed cycle; this is the main idea
of the rest of the steps. This kind of cycle do not exist for pairs
$P_{0},L_{\alpha^{2}}$ and $P_{1},L_{\alpha}$ as the mixed cycles of the form
$([m,b],P_{m},L_{x},(x,y))$ for which $y=mx+b$ were already erased in steps 1
and 2. For steps 4 and 5 it also holds that no new cycle is created, by a
similar argument as in step 3. The same applies to steps 6 and 7, where in
addition we can see that no new cycle is created by adding an arc between the
set of points adjacent to line $L$ and the set of lines adjacent to point $P$;
the arc added has the same direction as arc $(P,L)$ added in step 2. Step 8
can be seeing as a matching between lines missing out-arcs and points missing
in-arcs, in such a way that no new cycle is added. Finally, only
$[\alpha^{2},\alpha]$ and $(0,\alpha^{2})$ were missing one edge, which is
added in step 9, and no new cycle is added by the arcs already defined between
points and lines adjacent to $L_{0}$ and $P_{\alpha^{2}}$. ∎

Note that the graph $G_{(2,4)}$ is quite symmetrical. We were able to remove
lines and points on pairs. For example, the deletion of lines $[0,0]$ and
$[0,1]$, and points $(\alpha^{2},\alpha)$ and $(\alpha^{2},\alpha^{2})$
allowed to add arc $(P_{0},L_{\alpha^{2}})$ and no new cycle was created.
Other projective planes lack of this symmetric structure, meaning that only
removing certain lines and points is not enough to keep the girth equals to 6.
That is, it is needed to remove or direct further edges, resulting on a
complete different graph, if such graph exists. Based on this, we conjecture
that it is not possible to extend this construction using other finite fields
$\mathbb{F}_{q}$ to generate $[1,r,6]$-mixed cages for $r\geq 4$, $q$ a prime
power.

##  4 A family of mixed graphs with girth 6

In this section, we exhibit an infinity family of mixed graphs that have girth
6. We also show that this construction provides an upper bound for the minimum
order of $[z,r;6]$-mixed cages, for certain pairs of $z$ and $r$. The main
idea of our construction is to consider two copies of the undirected adjacency
graph corresponding to the biaffine plane and connect them using arcs.

Let $q$ be a prime. Consider the bipartite graph $B_{q}$ over $\mathbb{Z}_{q}$
described in Section 2. Take a copy of $B_{q}$ and refer to it as
$B^{\prime}_{q}$. For ease of notation, whenever $v^{\prime}\in
V(B^{\prime}_{q})$ appears, we assume that $v^{\prime}=v$, that is,
$v^{\prime}$ is the copy vertex of the original vertex $v\in V(B_{q})$;
similarly for edges.

Let $p\in\mathbb{Z}$ be an odd number such that $2q=4p+2$, or equivalently,
$p=\frac{q-1}{2}$.

We describe the construction of digraph $C_{m}$ for $m\in\mathbb{Z}_{q}$,
which is a similar digraph to a circulant graph
$\overset{\rightarrow}{C}_{2q}(1,3,5,\dots,p)$. We use a different notation as
the digraph we describe is also bipartite. $C_{m}$ has vertices
$\\{[m,b]\,|\,b\in\mathbb{Z}_{q}\\}\cup\\{[m^{\prime},b^{\prime}]\,|\,b\in\mathbb{Z}_{q}\\}$.
It has $p$ directed cycles, each one using the $2q$ vertices. A cycle consists
on arcs between original and copy-vertices. Let us fix the the following
ordering of the vertices by
$[m,0],[m^{\prime},0^{\prime}],[m,1],[m^{\prime},1^{\prime}],\dots,[m,q-1],[m^{\prime},(q-1)^{\prime}]$,
which we call the _alternating ordering_. Then, we say that a cycle _jumps_
between vertices with a fixed length $j$ with respect to the alternating
ordering if each of its arcs is of the form $(v_{i},v_{i+j\mod q})$ and either
($v_{i}\in V(B_{q})$ and $v^{\prime}_{i+j\mod q}\in V(B^{\prime}_{q})$) or
($v^{\prime}_{i}\in V(B^{\prime}_{q})$ and $v_{i+j\mod q}\in V(B_{q})$).
Hence, for a cycle that has jumps of length $j\in\\{1,3,5,\dots,p\\}$, this
cycle contains the arcs

$\displaystyle\left([m,b],[m^{\prime},(b+\frac{j-1}{2})^{\prime}]\right),$
$\displaystyle//\text{ {From original to copy}}$
$\displaystyle\left([m^{\prime},b^{\prime}],[m,b+\frac{j+1}{2}]\right),$
$\displaystyle//\text{ {From copy to original}}$

where the sums are taken in $\\!\\!\mod q$. Note that this is equivalent to
have arcs of type

$\displaystyle\left([m,b],[m^{\prime},(b+j)^{\prime}]\right)\quad
j\in\\{0,1,2,\dots,\frac{p-1}{2}\\},$ $\displaystyle//\text{ {From original to
copy}}$ $\displaystyle\left([m^{\prime},b^{\prime}],[m,b+j]\right)\quad
j\in\\{1,2,3,\dots,\frac{p+1}{2}\\},$ $\displaystyle//\text{ {From copy to
original}}$

In the same fashion, we construct digraph $C_{x}$ for $x\in B_{q}$. Figure 2
shows $C_{m}$ for $m\in\mathbb{Z}_{11}$.

$0^{\prime}$$0$$1^{\prime}$$1$$2^{\prime}$$2$$3^{\prime}$$3$$4^{\prime}$$4$$5^{\prime}$$5$$6^{\prime}$$6$$7^{\prime}$$7$$8^{\prime}$$8$$9^{\prime}$$9$$10^{\prime}$$10$
Figure 2: $C_{m}$ for $m\in\mathbb{Z}_{11}$, $p=5$. Node $[m,b]$ is written
simply by $b$. Original nodes are drawn in orange and copy nodes in blue.
Outside arcs have jumps of length 3 while inside arcs have jumps of length 5.
One shortest path is $(0,2^{\prime},5,7^{\prime},10,10^{\prime})$.

The following result is not difficult to see by the fact that $C_{m}$ and
$C_{x}$ are bipartite circulant graphs. Nonetheless, we show a proof for
completeness.

######  Lemma 4.

$C_{m}$ and $C_{x}$ are $[\frac{p+1}{2},0;6]$-mixed graphs for $m,x\in B_{q}$.

###### Proof.

Without loss of generality we prove the statement for $C_{m}$. First, by
construction each vertex clearly has $\frac{p+1}{2}$ in- and out-arcs, and $0$
edges.

$C_{m}$ has a cycle of length 6. This cycle uses four arcs that correspond to
jumps of length $p$ and then two arcs corresponding to jumps of length 1
(e.g., consider the cycle
$\left([m,0],[m^{\prime},(\frac{p-1}{2})^{\prime}],[m,p],[m^{\prime},(\frac{3p-1}{2})^{\prime}],[m,2p],\right.\allowbreak\left.[m^{\prime},(q-1)^{\prime}]\right)$).

We claim that there is no small cycle than this type. Suppose that $K$ is a
cycle of length smaller than 6. As $C_{m}$ is bipartite, then the length of
$K$ cannot be 5 or 3. This implies that $|K|=4$ as clearly $|K|=2$ is not
possible by construction. Let $j_{1},j_{3},j_{5},\dots,j_{p}$ be the length of
the jumps made by $K$ w.r.t. the alternating ordering. Then,

$2q=a_{1}j_{1}+a_{3}j_{3}+\dots+a_{p}j_{p}$ (2)

holds, where $a_{j}$ is the number of jumps of length $j$. By assumption on
the size of $K$, even giving four jumps of the largest length is not enough to
fulfill Equation 2 as $2q\neq 4p$. This shows that such cycle $K$ cannot
exists, concluding the proof. ∎

Finally, consider the mixed graph $G_{p,q}=\left(V(B_{q})\bigcup
V(B^{\prime}_{q}),E(B_{q})\bigcup
E(B^{\prime}_{q})\bigcup\limits_{m\in\mathbb{Z}_{q}}A(C_{m})\bigcup\limits_{x\in\mathbb{Z}_{q}}A(C_{x})\right)$.

Figure 3 shows the construction with parameters $q=3$ and $p=1$, which
determines a $[1,3;6]$-mixed graph.

######  Theorem 5.

For all $q\geq 3$ prime and $p=\frac{q-1}{2}$ such that $p$ is odd, the graph
$G_{p,q}$ is a $[\frac{p+1}{2},q,6]$-mixed graph.

###### Proof.

Parameters $\frac{p+1}{2}$ and $q$ are evident by construction and by 4. For
all $m,x\in\mathbb{Z}_{q}$, each digraph $C_{m}$ and $C_{x}$ has directed
girth 6 by 4. Similarly, the undirected graphs $B_{q}$ and $B^{\prime}_{q}$
have undirected girth 6 (see Section 2). We only need to verify that there is
no mixed cycle of length smaller than 6, that is, that no new mixed cycle is
formed by making the union of such graphs.

Suppose that $K$ is a mixed cycle so that $|K|<6$. It is not difficult to see
that $K$ cannot have length 2 nor 3.

We show that $|K|\neq 4$. As we only have arcs between lines (points) that
share the first same coordinate (one in vertex is in $B_{q}$ and the other in
$B^{\prime}_{q}$), in order to have a mixed cycle of length 4, we need two
edges: one in $B_{q}$ and one in $B^{\prime}_{q}$. Thus, we require two arcs,
one leaving $B_{q}$ (and entering $B^{\prime}_{q}$) and one entering it (and
leaving $B^{\prime}_{q}$). Consider a point $(x,mx+b)$ and its adjacent line
(by edge) $[m,b]$. We know that $(x,mx+b)$ is arc-adjacent to
$(x^{\prime},(mx+b+j)^{\prime})$ in $C_{x}$ with
$j\in\\{0,1,2\dots,\frac{p-1}{2}\\}$. By properties of $B^{\prime}_{q}$ (being
the copy of $B_{q}$), $(x^{\prime},(mx+b)^{\prime})$ is edge-adjacent to
$[m^{\prime},b^{\prime}]$. By construction, $[m,b]$ is arc-adjacent to
$[m^{\prime},(b+j)^{\prime}]$, implying that there is no mixed cycle of length
4.

We show that $|K|\neq 5$. To see this, note that the graph $G_{p,q}$ is a
mixed bipartite graph with parts
$\left\\{[m,b],(x^{\prime},y^{\prime})\,|\,m,b\in
V(B_{q}),\,x^{\prime},y^{\prime}\in V(B^{\prime}_{q})\right\\}$ and
$\left\\{[m^{\prime},b^{\prime}],(x,y)\,|\,m,b\in V(B^{\prime}_{q}),\,x,y\in
V(B_{q})\right\\}$. This implies that there is no mixed cycle of length 5. ∎

Note that $G_{p,q}$ has a lot of mixed cycles of length 6. To see this,
consider the points $(x_{1},mx_{1}+b)$ and $(x_{2},mx_{2}+b)$. Those points
intersect on line $[m,b]$. Let
$\left(x_{1}^{\prime},(mx_{1}+b+j)^{\prime}\right)$ be the vertex arc-adjacent
to $(x_{1},mx_{1}+b)$, for some $j\in\\{1,2,3,\dots,\frac{p+1}{2}\\}$. Also,
consider the vertex $\left(x_{2}^{\prime},(mx_{2}+b+j-1)^{\prime}\right)$
which is arc-adjacent to $(x_{2},mx_{2}+b)$. Clearly, points
$\left(x_{1}^{\prime},(mx_{1}+b+j)^{\prime}\right)$ and
$\left(x_{2}^{\prime},(mx_{2}+b+j-1)^{\prime}\right)$ intersect in line
$[m^{\prime},b^{\prime}]$. This implies that we can find the mixed cycle of
length 6

$\left((x_{1},mx_{1}+b),\left(x_{1}^{\prime},(mx_{1}+b+j)^{\prime}\right),[m^{\prime},b^{\prime}],\left(x_{2}^{\prime},(mx_{2}+b+j-1)^{\prime}\right),(x_{2},mx_{2}+b),[m,b]\right).$

Note that the assumption on $p$ being odd can also be modified to allow even
numbers. Hence, the jumps allowed on the circulant digraph are of the type
$\\{1,3,5,\dots,p-1\\}$.

######  Corollary 6.

For all $q\geq 3$ prime and $p=\frac{q-1}{2}$ such that $p$ is even, the graph
$G_{p,q}$ is a $[\frac{p}{2},q,6]$-mixed graph.

Finally, the following corollary on the order of a mixed cage is trivial.

######  Corollary 7.

Let $n[\frac{p+1}{2},q,6]$ be the minimum order of a
$[\frac{p+1}{2},q,6]$-mixed cage with $q\geq 3$ a prime and $p=\frac{q-1}{2}$
odd. Then, $n[z,r;g]\leq 4q^{2}$.

Figure 3 shows that our construction for the $[1,3;6]$-mixed graph contains 36
nodes, while the $[1,3;6]$-mixed cage has 30 nodes (see Section 3).

$(0,0)$$[0,0]$$(0^{\prime},0^{\prime})$$[0^{\prime},0^{\prime}]$$(0,1)$$[0,1]$$(0^{\prime},1^{\prime})$$[0^{\prime},1^{\prime}]$$(0,2)$$[0,2]$$(0^{\prime},2^{\prime})$$[0^{\prime},2^{\prime}]$$(1,0)$$[1,0]$$(1^{\prime},0^{\prime})$$[1^{\prime},0^{\prime}]$$(1,1)$$[1,1]$$(1^{\prime},1^{\prime})$$[1^{\prime},1^{\prime}]$$(1,2)$$[1,2]$$(1^{\prime},2^{\prime})$$[1^{\prime},2^{\prime}]$$(2,0)$$[2,0]$$(2^{\prime},0^{\prime})$$[2^{\prime},0^{\prime}]$$(2,1)$$[2,1]$$(2^{\prime},1^{\prime})$$[2^{\prime},1^{\prime}]$$(2,2)$$[2,2]$$(2^{\prime},2^{\prime})$$[2^{\prime},2^{\prime}]$
Figure 3: Construction for the $[1,3;6]$-mixed graph with 36 nodes.

##  5 Lower Bound for mixed cages

The family of mixed graphs of girth 6 inspired us for the following lower
bound on the minimum order of $[z,r;g]$-mixed cages. The main idea is as
follows. The circulant graph $\overset{\rightarrow}{C}_{q}(0,\dots,z)$ is one
of the smallest directed graphs that are $z$-regular with girth $g$, where
$q=z(g-1)+1$. Clearly, adding any new arc (and thus edge) to this digraph
creates a directed cycle. Consider $g$ consecutive nodes and add on them the
tree $\mathcal{T}_{r,g}$ obtained from Moore’s Lower bound as stated on
Section 2. This structure is clearly a lower bound for any $[z,r;g]$-mixed
cage. See Figure 4 for an example on with parameters $z=2,r=5,$ and $g=6$.

012345109876 Figure 4: Lower bound for a $[2,5;6]$-mixed cage with 11 + 66 - 6
= 69 nodes. Circulant graph has numbered vertices. The first level of vertices
of the tree is shown in thick orange.

######  Theorem 8.

Let $n[z,r;g]$ be the minimum order of a $[z,r;g]$-mixed cage. Then,
$n[z,r;g]\geq n[z,g]+n_{\text{AHM}}[1,r;g]-g$.

###### Proof.

Any lower bound of $n[z,r;g]$ requires as many nodes as any $z$-regular
directed graph with girth $g$. Over such digraph, we can take $g$ consecutive
nodes and add $\mathcal{T}_{r,g}$. This provides $n_{\text{AHM}}[1,r;g]-g$
nodes, concluding the proof. ∎

Based on 1, then we obtain the following.

######  Conjecture 9.

If 1 is true, then $n[z,r;g]\geq z(g-1)+1+n_{\text{AHM}}[1,r;g]-g$.

Note that if $z=1$ the lower bound provided in 8 coincides with the AHM bound,
but our construction contains an extra arc connecting the first and sixth
vertices on the first level.

## Conclusions

We provided a general lower bound for the minimum order of $[z,r;g]$-mixed
cages for any value of $z,r$, and $g$.

We obtained an infinity family of mixed graphs of girth 6 using the biaffine
plane. We also tried to generate families using the projective plane, but this
seems a more challenging problem. Furthermore, we conjecture that this is not
possible as the graphs generated by projective planes are already quite dense
(those are already undirected cages of girth 6). In this sense, the Galois
field of order 4 that generated the $[1,3;6]$-mixed cage is quite special. Its
symmetrical structure allowed us to safely remove points and lines, and add
the missing arcs.

There is still a long path to find families of girth 5 and 6 that provide
better upper bounds.

### Acknowledgments

We are thankful to György Kiss and to the Erasmus+20 scholarship to bring the
authors together.

#### Funding:

Gabriela Araujo-Pardo was supported by PAPIIT-UNAM-México IN101821 and
Proyecto de Intercambio Académico de la Coordinación de la Investigación
Científica de la UNAM ”Bipartite biregular cages, block designs and
generalized quadrangles”. Lydia Mirabel Mendoza-Cadena was supported by the
Lendület Programme of the Hungarian Academy of Sciences – grant number
LP2021-1/2021.

## References

  * [1] G. Araujo-Pardo, C. Hernández-Cruz, J. J. Montellano-Ballesteros, Mixed cages, Graphs and Combinatorics 35 (5) (2019) 989–999.  doi:https://doi.org/10.1007/s00373-019-02050-1.
  * [2] G. Exoo, R. Jajcay, Dynamic cage survey, The electronic journal of combinatorics (2013).  doi:https://doi.org/10.37236/37.
  * [3] G. Exoo, On Mixed Cages, Discrete Mathematics & Theoretical Computer Science vol. 25:2 (Nov. 2023).  doi:10.46298/dmtcs.11057.
URL https://dmtcs.episciences.org/12615

  * [4] G. Araujo-Pardo, C. De la Cruz, D. González-Moreno, Mixed cages: Monotonicity, connectivity and upper bounds, Discrete Mathematics 345 (5) (2022) 112792.  doi:https://doi.org/10.1016/j.disc.2021.112792.
URL https://www.sciencedirect.com/science/article/pii/S0012365X21005057

  * [5] M. Miller, J. Sirán, Moore graphs and beyond: A survey of the degree/diameter problem, The electronic journal of combinatorics (2013).  doi:https://doi.org/10.37236/35.
  * [6] P. R. Hafner, Geometric realisation of the graphs of Mckay–Miller–Širáň, Journal of Combinatorial Theory, Series B 90 (2) (2004) 223–232.  doi:https://doi.org/10.1016/j.jctb.2003.07.002.
URL https://www.sciencedirect.com/science/article/pii/S0095895603000868

  * [7] G. Araujo, M. Noy, O. Serra, A geometric construction of large vertex transitive graphs of diameter two, Journal of Combinatorial Mathematics and Combinatorial Computing 57 (2006) 97.
  * [8] G. Araujo-Pardo, C. Balbuena, M. Miller, M. Ždímalová, A family of mixed graphs with large order and diameter 2, Discrete Applied Mathematics 218 (2017) 57–63.  doi:https://doi.org/10.1016/j.dam.2016.09.034.
URL https://www.sciencedirect.com/science/article/pii/S0166218X16304401

  * [9] M. Behzad, G. Chartrand, C. E. Wall, On minimal regular digraphs with given girth, Fundamenta Mathematicae 69 (3) (1970) 227–231.  doi:10.4064/fm-69-3-227-231.
URL http://eudml.org/doc/214245

  * [10] G. Araujo-Pardo, C. Balbuena, M. Olsen, On (k, g; l)-dicages, Ars Combinatoria 92 (2009) 289–301.