# On large regular $(1,1,k)$-mixed graphs

C. Dalfóa, G. Erskineb, G. Exooc, M. A. Fiold,
N. Lópeza, A. Messeguéa, J. Tuiteb

aDept. de Matemàtica, Universitat de Lleida, Catalonia
<EMAIL_ADDRESS><EMAIL_ADDRESS>
bSchool of Mathematics and Statistics, Open University, Milton Keynes, UK
<EMAIL_ADDRESS>
cDept. of Mathematics and Computer Science, Indiana State University, USA
<EMAIL_ADDRESS>
dDept. de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona,
Catalonia
Barcelona Graduate School of Mathematics
Institut de Matemàtiques de la UPC-BarcelonaTech (IMTech)
<EMAIL_ADDRESS>
###### Abstract

An $(r,z,k)$-mixed graph $G$ has every vertex with undirected degree $r$,
directed in- and out-degree $z$, and diameter $k$. In this paper, we study the
case $r=z=1$, proposing some new constructions of $(1,1,k)$-mixed graphs with
a large number of vertices $N$. Our study is based on computer techniques for
small values of $k$ and the use of graphs on alphabets for general $k$. In the
former case, the constructions are either Cayley or lift graphs. In the latter
case, some infinite families of $(1,1,k)$-mixed graphs are proposed with
diameter of the order of $2\log_{2}N$.

Keywords: Mixed graph, Moore bound, Cayley graph, Lift graph.

Mathematics Subject Classification: 05C50, 05C20, 15A18, 20C30.

##  1 Introduction

The relationship between vertices or nodes in interconnection networks can be
undirected or directed depending on whether the communication between nodes is
two-way or only one-way. Mixed graphs arise in this case and in many other
practical situations, where both kinds of connections are needed. Urban street
networks are perhaps the most popular ones. Thus, a mixed graph  $G=(V,E,A)$
has a set $V=V(G)=\\{u_{1},u_{2},\ldots\\}$ of vertices, a set $E=E(G)$ of
edges or unordered pairs of vertices $\\{u,v\\}$, for $u,v\in V$, and a set
$A=A(G)$ of arcs, directed edges, or ordered pair of vertices $uv\equiv(u,v)$.
For a given vertex $u$, its undirected degree $r(u)$ is the number of edges
incident to vertex $u$. Moreover, its out-degree $z^{+}(u)$ is the number of
arcs emanating from $u$, whereas its in-degree $z^{-}(u)$ is the number of
arcs going to $u$. If $z^{+}(u)=z^{-}(u)=z$ and $r(u)=r$, for all $u\in V$,
then $G$ is said to be a totally regular $(r,z)$-mixed graph with whole degree
$d=r+z$.

The distance from vertex $u$ to vertex $v$ is denoted by $\mathrm{dist}(u,v)$.
Notice that, when the out-degree $z$ is not zero, the distance
$\mathrm{dist}(u,v)$ is not necessarily equal to the distance
$\mathrm{dist}(v,u)$. If the mixed graph $G$ has diameter $k$, its distance
matrix $\mbox{\boldmath$A$}_{i}$, for $i=0,1,\ldots,k$, has entries
$(\mbox{\boldmath$A$}_{i})_{uv}=1$ if $\mathrm{dist}(u,v)=i$, and
$(\mbox{\boldmath$A$}_{i})_{uv}=0$ otherwise. So,
$\mbox{\boldmath$A$}_{0}=\mbox{\boldmath$I$}$ (the identity matrix) and
$\mbox{\boldmath$A$}_{1}=\mbox{\boldmath$A$}$ (the adjacency matrix of $G$).

Mixed graphs were first considered in the context of the degree/diameter
problem by Bosák [2]. The degree/diameter problem for mixed graphs reads as
follows: Given three natural numbers $r$, $z$, and $k$, find the largest
possible number of vertices $N(r,z,k)$ in a mixed graph $G$ with maximum
undirected degree $r$, maximum directed out-degree $z$, and diameter $k$.

For mixed graphs, an upper bound for $N(r,z,k)$, known as a Moore$($-like$)$
bound $M(r,z,k)$, was obtained by Buset, El Amiri, Erskine, Miller, and Pérez-
Rosés [3] (also by Dalfó, Fiol, and López [8] with an alternative
computation).

######  Theorem 1.1 (Buset, El Amiri, Erskine, Miller, and Pérez-Rosés [3]).

The Moore bound for an $(r,z)$-mixed graph with diameter $k$ is

$M(r,z,k)=A\frac{u_{1}^{k+1}-1}{u_{1}-1}+B\frac{u_{2}^{k+1}-1}{u_{2}-1},$ (1)

where

$\displaystyle u_{1}$
$\displaystyle=\displaystyle{\frac{z+r-1-\sqrt{v}}{2}},\qquad
u_{2}=\displaystyle{\frac{z+r-1+\sqrt{v}}{2}},$ $\displaystyle A$
$\displaystyle=\displaystyle{\frac{\sqrt{v}-(z+r+1)}{2\sqrt{v}}},\qquad
B=\displaystyle{\frac{\sqrt{v}+(z+r+1)}{2\sqrt{v}}},$ $\displaystyle v$
$\displaystyle=(z+r)^{2}+2(z-r)+1.$

This bound applies whether or not $G$ is totally regular, but it is elementary
to show that a Moore mixed graph must be totally regular. Thus, a Moore
$(r,z,k)$-mixed graph is a graph with diameter $k$, maximum undirected degree
$r\geq 1$, maximum out-degree $z\geq 1$, and order given by $M(r,z,k)$. An
example of a Moore $(3,1,2)$-mixed graph is the Bosák graph [2], see Figure 1.

Figure 1: The Bosák $(3,1)$-graph with diameter $k=2$ and $N=18$ vertices.

Bosák [2] gave a necessary condition for the existence of a mixed Moore graph
with diameter $k=2$. Such graphs have the property that for any ordered pair
$(u,v)$ of vertices, there is a unique walk of length at most $2$ between
them. In general, there are infinitely many pairs $(r,z)$ satisfying Bosák
necessary condition for which the existence of a mixed Moore graph is not
known yet. Nguyen, Miller, and Gimbert [24] proved the existence and unicity
of some Moore mixed graphs of diameter 2. López, Miret, and Fernández, [20]
proved that there is no Moore $(r,z,2)$-mixed graph when the pair $(r,z)$
equals $(3,3)$, $(3,4)$, or $(7,2)$.

For diameter $k\geq 3$, it was proved that mixed Moore graphs do not exist,
see Nguyen, Miller, and Gimbert [24]. In the case of total regularity, this
result also follows from the improved bound in Dalfó, Fiol, and López [8],
where it was shown that the order $N$ of an $(r,z)$-regular mixed graph G with
diameter $k\geq 3$ satisfies

$N\leq M(r,z,k)-r,$ (2)

where $M(r,z,k)$ is given by (1). In general, a mixed graph with maximum
undirected degree $r$, maximum directed out-degree $z$, diameter $k$, and
order $N=M(r,z,k)-\delta$ is said to have defect $\delta$. A mixed graph with
defect one is called an almost mixed Moore graph. Thus, the result in (2) can
be rephrased by saying that $r$ is a lower bound for the defect of the mixed
graph. In the case $r=z=1$, such a result was drastically improved by Tuite
and Erskine [27] by showing that a lower bound $\delta(k)$ for the defect of a
$(1,1)$-regular mixed graph with diameter $k\geq 1$ satisfies the recurrence

$\delta(k+6)=\delta(k)+f_{k-1}+f_{k+4},$ (3)

where the initial values of $\delta(k)$, for $k=1,\ldots,6$, are
$0,1,1,2,3,5$, and $f_{k}$ are the Fibonacci numbers starting from
$f_{0}=f_{1}=1$, namely, $1,1,2,3,5,8,13,21,\ldots$ Alternatively, starting
from $\delta(1)=0$ and $\delta(2)=1$, we have
$\delta(k+2)=\delta(k+1)+\delta(k)$ if $k+2\not\equiv 1,2\ (\textrm{mod}\ 6)$,
and $\delta(k+2)=\delta(k+1)+\delta(k)+1$, otherwise.

For more results on degree/diameter problem for graphs, digraphs, and mixed
graphs, see the comprehensive survey by Miller and Širáň [23]. For more
results on mixed graphs, see Buset, López, and Miret [4], Dalfó [5], Dalfó,
Fiol, and López [7, 8, 9], Erskine [13], Jørgensen [18], López, Pérez-Rosés,
and Pujolàs [21], Nguyen, Miller, and Gimbert [24], and Tuite and Erskine
[26].

In this paper, we deal with $(1,1,k)$-mixed graphs, that is, mixed graphs with
undirected degree $r=1$, directed out-degree $z=1$, and with diameter $k$. Our
study is based on computer techniques for small values of $k$, and the use of
graphs on alphabets for general $k$. In the former case, the constructions are
either Cayley or lift graphs. In the latter case, some infinite families of
$(1,1,k)$-mixed graphs are proposed with $N$ vertices and diameter $k$ of the
order of $2\log_{2}N$. Most of the proposed constructions are closely related
to line digraphs. Given a digraph $G$, its line digraph $LG$ has vertices
representing the arcs of $G$, and vertex $x_{1}x_{2}$ is adjacent to vertex
$y_{1}y_{2}$ in $LG$ if the arc $(x_{1},x_{2})$ is adjacent to the arc
$(y_{1},y_{2})$ in $G$, that is, if $y_{1}=x_{2}$. The $k$-iterated line
digraph is defined recursively as $L^{k}G=L^{k-1}(LG)$. Let $K_{d}^{+}$ be the
complete symmetric digraph with $d$ vertices with loops, and $K_{d+1}$ the
complete symmetric digraph on $d+1$ vertices (in these complete graphs each
edge is seen as a digon, or pair of opposite arcs). Then, two well know
families of iterated line digraphs are the De Bruijn digraphs
$B(d,k)=L^{k}(K_{d}^{+})$, and the Kautz digraphs $K(d,k)=L^{k}(K_{d+1})$.
Both $B(d,k)$ and $K(d,k)$ have diameter $k$ but De Bruijn digraphs have
$d^{k}$ vertices, whereas Kautz digraphs have $d^{k}+d^{k-1}$ vertices. See,
for instance, Fiol, Yebra, and Alegre [15], and Miller and Širáň [23].

##  2 Some infinite families of $(1,1,k)$-mixed graphs

In this section, we propose some infinite families of $(1,1,k)$-mixed graphs
with exponential order. All of them have vertices with out-degree $z=1$. When,
moreover, all the vertices have in-degree $1$, we refer to them as
$(1,1,z)$-regular mixed graphs. If we denote by $f(r,z,k)$ the order of a
largest $(r,z,k)$-mixed graph, which is upper bounded by the (exponential)
Moore bound $M(r,z,k)$, all the described graphs provide exponential lower
bounds for $f(1,1,k)$.

Let us first give some basic properties of $(1,1,k)$-mixed graphs. It is
readily seen that the Moore bound satisfies the Fibonacci-type recurrence

$M(1,1,k)=M(1,1,k-1)+M(1,1,k-2)-2,$

starting from $M(1,1,0)=1$ and $M(1,1,1)=3$. From this, or just applying (1),
we obtain that the corresponding Moore bound is

$M(1,1,k)=\left(1-\frac{2}{\sqrt{5}}\right)\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}+\left(1+\frac{2}{\sqrt{5}}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-2.$
(4)

The obtained values for $k=2,\ldots,16$ are shown in Table 4. Then, for large
values of $k$, the Moore bound $M(1,1,k)$ is of the order of

$M(1,1,k)\sim\left(1+\frac{2}{\sqrt{5}}\right)\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}\approx
1.8944\cdot 1.6180^{k+1}.$

###  2.1 The mixed graphs $E(n)$

The first construction is the simplest one. Given $n\geq 2$, the graph $E(n)$
is defined as follows. As before, label the Fibonacci numbers so that
$f_{0}=f_{1}=1$. Consider a Moore tree of radius $n$ with base vertex $u_{0}$.
The set of vertices at distance $i$ from $u_{0}$ is referred to as the
vertices at level $i$. There are $f_{i+1}$ vertices at level $i$. We can
partition these vertices into two sets: $V_{i}$ contains the $f_{i}$ vertices
at level $i$ incident through an arc from level $i-1$, and $W_{i}$ contains
the $f_{i-1}$ vertices at level $i$ incident through an edge from level $i-1$.

To complete the graph, we must consider two cases, depending on whether
$f_{n}$ is even or odd. If $f_{n}$ is even, then we add a matching among the
vertices of $V_{n}$ and add an arc from each vertex in level $n$ to $u_{0}$.
In this case, the diameter is $2n$. Note that the maximum distance occurs from
a level-1 vertex to a level-t vertex on the opposite edge (where the two edges
are based on the two level-1 vertices).

If $f_{n}$ is odd, then we must modify the construction slightly. In this
case, when we add a matching among the vertices of $V_{n}$, there is one
vertex $v_{1}$ of $V_{n}$ missed by the matching. So, we must add another
vertex $v_{2}$, join this vertex to $v_{1}$ by an edge, and then add an arc
from $v_{2}$ to the base vertex $u_{0}$. All other vertices at level $n$ have
arcs directly to $u_{0}$. In this case, the diameter is $2n+1$, where the
maximum distance occurs from a level-1 vertex (in the edge not containing
$v_{1}$) to $v_{2}$.

So, the graph $E(n)$ has diameter $2n$ or $2n+1$, and order $M(1,1,n)$ or
$M(1,1,n)+1$. This bound is very weak for small diameters but at least it
gives a first explicit construction that gives an exponential lower bound. In
the following subsections, we show that we can do it better.

###  2.2 The mixed graphs $F(n)$

Given $n\geq 2$, the $(1,1,k)$-mixed graph $F(n)$ has vertices labeled with
$a:x_{1}\ldots x_{n}$, where $a\in\\{+1,-1\\}$, with $x_{i}\in\mathbb{Z}_{3}$,
and $x_{i+1}\neq x_{i}$ for $i=1,\ldots,n-1$. The adjacencies are as follows:

  * $(i)$

$a:x_{1}x_{2}\ldots x_{n}\,\sim\,-a:x_{1}x_{2}\ldots x_{n}$ (edges);

  * $(ii)$

$a:x_{1}x_{2}\ldots x_{n}\,\rightarrow\,a:x_{2}x_{3}\ldots x_{n}(x_{n}+a)$
(arcs).

Thus, $F(n)$ has $3\cdot 2^{n}$ vertices, it is an out-regular graph but not
in-regular since vertices $a:x_{1}x_{2}\ldots x_{n}$ and
$a:x^{\prime}_{1}x_{2}\ldots x_{n}$ are both adjacent to
$a:x_{2}\ldots(x_{n}+a)$.

Figure 2: The mixed graph $F(3)$.

The mixed graph $F(3)$ is shown in Figure 2. It is easily checked that the
mapping

$a|x_{1}x_{2}\ldots
x_{n}\quad\mapsto\quad-a|\overline{x_{1}}\,\overline{x_{2}}\ldots\overline{x_{n}},$
(5)

where $\overline{0}=1$, $\overline{1}=0$, and $\overline{2}=2$, is an
automorphism of $F(n)$. This is because
$\overline{x_{n}+a}=\overline{x_{n}}-a$.

######  Proposition 2.1.

The diameter of the mixed graph $F(n)$ is $k=2n$.

###### Proof.

Let us see that there is a path of length at most $2n$ from vertex
$\mbox{\boldmath$x$}=a|x_{1}\ldots x_{n}$ to vertex
$\mbox{\boldmath$y$}=b|y_{1}\ldots y_{n}$. Taking into account the
automorphism in (5), we can assume that $a=+1$. Notice that, with at most two
steps, depending on the values of $a$, $x_{n}$, and $y_{1}$ (at the beginning)
or $a$, $y_{i}$, and $y_{i+1}$ (in the sequel), we can add a new digit of $y$.
Thus, in principle, we would need at most $2n$ steps but, possibly, one last
step to fix the first digit to the one of $y$ (for example, $b$). However, in
what follows, we show that the first two digits $y_{1}$ and $y_{2}$ can be
‘placed’, so reaching a vertex of the form $a^{\prime}|\ldots y_{1}y_{2}$,
with at most 3 steps.

  * •

If $y_{1}=x_{n}$, the first step is not necessary.

  * •

If $y_{1}=x_{n}+1$, go through the arc $+1|x_{1}\ldots
x_{n}\rightarrow+1|x_{2}\ldots x_{n}y_{1}$.

  * •

If $y_{1}=x_{n}-1$ and $y_{2}=y_{1}-1$, go through the edge and two arcs

$+1|x_{1}\ldots x_{n}\sim-1|x_{1}x_{2}\ldots x_{n}\rightarrow-1|x_{2}\ldots
x_{n}y_{1}\rightarrow-1|x_{3}\ldots x_{n}y_{1}y_{2}.$

  * •

If $y_{1}=x_{n}-1(=x_{n}+2)$ and $y_{2}=y_{1}+1$, go through the three arcs

$\displaystyle+1|x_{1}\ldots x_{n}$ $\displaystyle\rightarrow+1|x_{2}\ldots
x_{n}x_{n}+1\rightarrow+1|x_{3}\ldots x_{n}+1x_{n}+2$
$\displaystyle=+1|x_{3}\ldots x_{n}+1y_{1}\rightarrow+1|x_{4}\ldots
x_{n}y_{1}y_{2}.$

Thus, to reach $y$, we need at most $3+2(n-2)+1=2n$ steps. Finally, it is not
difficult to find vertices that are at distance $2n$. For instance, for $n$
odd, go from $\mbox{\boldmath$x$}=+1|0101\ldots 0$ to
$\mbox{\boldmath$y$}=-1|2020\ldots 2$; and, for $n$ even, go from
$\mbox{\boldmath$x$}=+1|1010\ldots 0$ to $\mbox{\boldmath$y$}=+1|2020\ldots
0$, ∎

####  2.2.1 A numeric construction

An alternative presentation $F[n]$ of $F(n)$ is as follows: Given $n\geq 1$,
let $N^{\prime}=3\cdot 2^{n-1}$ so that the number of vertices of $F[n]$ is
$2N^{\prime}$. The vertices of $F[n]$ are labeled as $\alpha|i$, where
$\alpha\in\\{1,2\\}$, and $i\in\mathbb{Z}_{N^{\prime}}$. Let $\overline{1}=2$
and $\overline{2}=1$. Then, the adjacencies of $F[n]$ defining the same mixed
graph as those in $(i)$ and $(ii)$ are:

$\displaystyle\alpha|i\,$ $\displaystyle\sim\,\overline{\alpha}|i\mbox{\
(edges);}$ (6) $\displaystyle\alpha|i\,$
$\displaystyle\rightarrow\,\alpha|-2i+\alpha\mbox{\ (arcs).}$ (7)

To show that both constructions give the same mixed graph, $F[n]\cong F(n)$,
define first the mapping $\pi$ from the two digits $x_{1}x_{2}$ to
$\mathbb{Z}_{6}$ as follows

$\pi(01)=0,\ \pi(10)=1,\ \pi(12)=2,\ \pi(21)=3,\ \pi(20)=4,\pi(02)=5.$

Then, it is easy to check that, for $n=2$, the mapping $\psi$ from the
vertices of $F(2)$ to the vertices of $F[2]$ defined as

$\psi(a|x_{1}x_{2})=\alpha(a)|\pi(x_{1}x_{2}),$

where $\alpha(a)=\frac{a+3}{2}$, is an isomorphism from $F(2)$ to $F[2]$.
(Note that $\alpha(-1)=1$ and $\alpha(+1)=2$). From this, we can use
induction. First, let us assume that $\psi^{\prime}$ is an isomorphism from
$F(n-1)$ to $F[n-1]$ of the form

$\psi^{\prime}(a|x_{1}x_{2}\ldots
x_{n-1})=\alpha(a)|\pi^{\prime}(x_{1}x_{2}\ldots x_{n-1}),$

where the linear mapping $\alpha$ is defined as above, and $\pi^{\prime}$ is a
mapping from the sequences $x_{1}x_{2}\ldots x_{n-1}$ to the elements of
$\mathbb{Z}_{N^{\prime}}$, with $N^{\prime}=3\cdot 2^{n-1}$. Then, we claim
that the mapping $\psi$ from the vertices of $F(n)$ to the vertices of $F[n]$
defined as

$\psi(a|x_{1}x_{2}\ldots x_{n})=\alpha(a)|-2\cdot\pi^{\prime}(x_{1}x_{2}\ldots
x_{n-1})+\alpha(x_{n}-x_{n-1})\ (\textrm{mod}\ N),$ (8)

where $N=3\cdot 2^{n}$, is an isomorphism from $F(n)$ to $F[n]$. Indeed, since
$\psi^{\prime}$ is an isomorphism from $F(n-1)$ to $F[n]$, we have that
$\psi^{\prime}\Gamma=\Gamma\psi^{\prime}$ and
$\psi^{\prime}\Gamma^{+}=\Gamma^{+}\psi^{\prime}$, where $\Gamma$ and
$\Gamma^{+}$ denote undirected and directed adjacency, respectively. Thus,
from

$\displaystyle\psi^{\prime}\Gamma(a|x1\ldots x_{n-1})$
$\displaystyle=\psi^{\prime}(-a|x_{1}\ldots
x_{n-1})=\alpha(-a)|\pi^{\prime}(x_{1}\ldots x_{n-1}),$
$\displaystyle\Gamma\psi^{\prime}(a|x_{1}\ldots x_{n-1})$
$\displaystyle=\Gamma(\alpha(a)|\pi^{\prime}(x_{1}\ldots
x_{n-1})=\overline{\alpha(a)}|\pi^{\prime}(x_{1}\ldots x_{n-1}),$

and

$\displaystyle\psi^{\prime}\Gamma^{+}(a|x_{1}\ldots x_{n-1})$
$\displaystyle=\psi^{\prime}(a|x_{2}\ldots
x_{n-1}x_{n-1}+a)=\alpha(a)|\pi^{\prime}(x_{2}\ldots x_{n-1}x_{n-1}+a),$
$\displaystyle\Gamma^{+}\psi^{\prime}(a|x_{1}\ldots x_{n-1})$
$\displaystyle=\Gamma^{+}(\alpha(a)|\pi^{\prime}(x_{1}\ldots
x_{n-1}))=\alpha(a)|-2\cdot\pi^{\prime}(x_{1}\ldots x_{n-1})+\alpha(a),$

we conclude that $\alpha(-a)=\overline{\alpha(a)}$ for every $a\in\\{+1,-1\\}$
(as it is immediate to check), and

$\pi^{\prime}(x_{2}\ldots x_{n-1}(x_{n-1}+a))=-2\cdot\pi^{\prime}(x_{1}\ldots
x_{n-1})+\alpha(a).$ (9)

Now, we can assume that $a=+1$ (because of the automorphism (5)), and let
$a^{\prime}=x_{n}-x_{n-1}$. Then, since clearly $\psi\Gamma=\Gamma\psi$, edges
map to edges, we focus on proving that the same holds for the arcs, that is,
$\psi^{+}\Gamma=\Gamma\psi^{+}$. With this aim, we need to prove that the
following two calculations, where we use (8), give the same result:

$\displaystyle\psi\Gamma^{+}(+1|x_{1}\ldots x_{n})$
$\displaystyle=\psi(+1|x_{2}\ldots x_{n}x_{n}+1)$
$\displaystyle=2|-2\cdot\pi^{\prime}(x_{2}\ldots x_{n})+2,$ (10)
$\displaystyle\Gamma^{+}\psi(+1|x_{1}\ldots x_{n})$
$\displaystyle=\Gamma^{+}(-2\cdot\pi^{\prime}(x_{1}\ldots
x_{n-1})+\alpha(a^{\prime})$ $\displaystyle=2|4\cdot\pi^{\prime}(x_{1}\ldots
x_{n-1})-2\alpha(a^{\prime})+2.$ (11)

The required equality follows since, from (9) with $a^{\prime}$ instead of
$a$, we have

$\displaystyle-2\cdot\pi^{\prime}(x_{2}\ldots x_{n})$
$\displaystyle=2\cdot\pi^{\prime}(x_{2}\ldots
x_{n-1}(x_{n-1}+a^{\prime}))=-2[-2\cdot\pi^{\prime}(x_{1}\ldots
x_{n-1})+\alpha(a^{\prime})]$ $\displaystyle=4\cdot\pi^{\prime}(x_{1}\ldots
x_{n-1})-2\alpha(a^{\prime}).$

In Figure 2, every vertex has been labeled according to both presentations.
Using this presentation, we extend (and again prove) Proposition 2.1.

######  Proposition 2.2.

The diameter of $F(n)$ is $k=2n$. More precisely, there is a path of length
$n$ or $n-1$ between any pair of edges $\alpha|i-\overline{\alpha}|i$ and
$\alpha^{\prime}|i^{\prime}-\overline{\alpha^{\prime}}|i^{\prime}$. Moreover,
there is a path of length between $n-1$ and $2n$ between any pair of vertices.

###### Proof.

Let us consider a tree rooted at a pair of vertices of an edge,
$\mbox{\boldmath$u$}_{1}=1|i$ and $\mbox{\boldmath$u$}_{2}=2|i$, and suppose
the $n=2r+1$ is odd (the case of even $n$ is similar). Then,

  * •

The vertices at distances $1,2$ of $\mbox{\boldmath$u$}_{1}$ or
$\mbox{\boldmath$u$}_{2}$ are $\alpha|-2i+1$, $\alpha|-2i+2$ with
$\alpha=1,2$.

  * •

The vertices at distances $3,4$ of $\mbox{\boldmath$u$}_{1}$ or
$\mbox{\boldmath$u$}_{2}$ are $\alpha|4i$, $\alpha|4i-1$, $\alpha|4i-2$ and
$\alpha|4i-3$ with $\alpha=1,2$.

  * •

The vertices at distances $5,6$ of $\mbox{\boldmath$u$}_{1}$ or
$\mbox{\boldmath$u$}_{2}$ are $\alpha|-8i+1$, $\alpha|-8i+2$, …,
$\alpha|-8i+8$ with $\alpha=1,2$.

  * ⋮

  * •

The vertices at distances $2n-3,2n-2$ of $\mbox{\boldmath$u$}_{1}$ or
$\mbox{\boldmath$u$}_{2}$ are $\alpha|2^{n-1}+r$ with
$r=0,-1,\ldots,-2^{n-1}+1$ and $\alpha=1,2$.

  * •

The vertices at distances $2n-1,2n$ of $\mbox{\boldmath$u$}_{1}$ or
$\mbox{\boldmath$u$}_{2}$ are $\alpha|-2^{n}+r$ with $r=1,2,\ldots,2^{n}$ and
$\alpha=1,2$.

See Figure 3 for the case of $F(3)$, which has $24$ vertices. Note that, from
the pair of vertices $1|i$ and $2|i$, the $3$-rd and $4$-th columns contain
all the ‘consecutive’ vertices of $F(3)$ from $\alpha|4i-3$ to $a|4i+8$, with
$\alpha=1,2$. More precisely, from vertex $2|i$ (we can fix $\alpha$ because
of the automorphism), we reach all of such vertices with at most $6$ steps,
except $2|4i+1$ (in boldface, on the top of the $4$-th column), which would
require the $7$ adjacencies ‘$-\rightarrow-\rightarrow-\rightarrow-$’. But
this vertex is reached following the path
‘$\rightarrow\rightarrow\rightarrow-\rightarrow-$’ (in boldface, in the $5$-th
column). In general, using the notation $f(\alpha|i)=\alpha|-2i+\alpha$ and
$g(\alpha|i)=\overline{\alpha}|i$, we have the following: Let
$N^{\prime}=3\cdot 2^{n-1}$. Then,

  * •

If $n$ is even, then the exception vertex is $g(fg)^{n}(2|i)(\textrm{mod}\
N)=1|2^{n}i$ ($2n+1$ steps) but $(gf)^{n-1}f^{2}(2|i)(\textrm{mod}\
N)=1|2^{n}i$ ($2n$ steps).

  * •

If $n$ is odd, then the exception vertex is $g(fg)^{n}(2|i)(\textrm{mod}\
N)=2|2^{n-1}i+1$ ($2n+1$ steps) but $(gf)^{n-1}f^{2}(2|i)(\textrm{mod}\
N)=2|2^{n-1}i+1$ ($2n$ steps).

∎

$\begin{array}[]{ccccccccc}&&&&&&2|-8i+1={\bf 2|4i+1}&&\\\ &&&&&&\vline&&\\\
&&&&1|4i&\longrightarrow&1|-8i+1=1|4i+1&&\\\ &&&&\vline&&&&\\\
&&2|-2i+1&\longrightarrow&2|4i&\longrightarrow&2|-8i+2=2|4i+2&&\\\
&&\vline&&&&\vline&&\\\ &&\vline&&&&1|-8i+2=1|4i+2&&\\\ &&\vline&&&&&&\\\
&&\vline&&&&2|-8i+3=2|4i+3&&\\\ &&\vline&&&&\vline&&\\\
1|i&\longrightarrow&1|-2i+1&\longrightarrow&1|4i-1&\longrightarrow&1|-8i+3=1|4i+3&&\\\
\vline&&&&\vline&&&&\\\ \vline&&&&2|4i-1&\longrightarrow&2|-8i+4=2|4i+4&&\\\
\vline&&&&&&\vline&&\\\ \vline&&&&&&1|-8i+4=1|4i+4&&\\\ \vline&&&&&&&&\\\
\vline&&&&&&2|-8i+5=2|4i+5&&\\\ \vline&&&&&&\vline&&\\\
\vline&&&&1|4i-2&\longrightarrow&1|-8i+5=1|4i+5&&\\\ \vline&&&&\vline&&&&\\\
2|i&\longrightarrow&2|-2i+2&\longrightarrow&2|4i-2&\longrightarrow&2|-8i+6=2|4i+6&&\\\
&&\vline&&&&\vline&&\\\ &&\vline&&&&1|-8i+6=1|4i+6&\rightarrow&1|4i+1\\\
&&\vline&&&&&&\vline\\\ &&\vline&&&&2|-8i+7=2|4i+7&&{\bf 2|4i+1}\\\
&&\vline&&&&\vline&&\\\
&&1|-2i+2&\longrightarrow&1|4i-3&\longrightarrow&1|-8i+7=1|4i+7&&\\\
&&&&\vline&&&&\\\ &&&&2|4i-3&\longrightarrow&2|-8i+8=2|4i+8&&\\\
&&&&&&\vline&&\\\ &&&&&&1|-8i+8=1|4i+8&&\end{array}$ Figure 3: The paths of
length at most $6$ in $F(3)$ from the vertices of the edge $\\{1|i,2|i\\}$.

###  2.3 The mixed graphs $F^{*}(n)$

A variation of the mixed graphs $F(n)$ allows us to obtain $(1,1,k)$-regular
mixed graphs that we denote $F^{*}(n)$. Given $n\geq 2$, the $(1,1,k)$-regular
mixed graph $F^{*}(n)$ has vertices labeled as those of $F(n)$. That is,
$a|x_{1}\ldots x_{n}$, where $a\in\\{+1,-1\\}$ and $x_{i}\in\mathbb{Z}_{3}$.
Now the adjacencies are as follows:

$\displaystyle a|x_{1}x_{2}\ldots x_{n}\,$
$\displaystyle\sim\,-a|x_{1}x_{2}\ldots x_{n}\mbox{\ (edges);}$ (12)
$\displaystyle a|x_{1}x_{2}\ldots x_{n}\,$
$\displaystyle\rightarrow\,a|x_{2}x_{3}\ldots
x_{n}(x_{n}+a(x_{2}-x_{1}))\mbox{\ (arcs)},$ (13)

where, when computed modulo 3, we take $x_{2}-x_{1}\in\\{+1,-1\\}$. Hence, the
vertices $a|x_{1}x_{2}\ldots x_{n}$ and $a|x^{\prime}_{1}x_{2}\ldots x_{n}$,
with $x_{1}^{\prime}\neq x_{1}$, are adjacent to different vertices of the
form $a|x_{2}\ldots(x_{n}\pm 1)$.

For example, the mixed graph $F^{*}(3)$ is shown in Figure 4.

Figure 4: The mixed graph $F^{*}(3)$.

####  2.3.1 An alternative presentation

To study some properties of $F^{*}(n)$, it is useful to work with the
following equivalent presentation: The vertices are now labeled as
$a|b:a_{1}\ldots a_{n-1}$, where $a,a_{i}\in\\{+1,-1\\}$ for $i=1,\ldots,n-1$,
and $b\in\mathbb{Z}_{3}$. Then, the adjacencies (12) and (13) become

$\displaystyle a|b:a_{1}a_{2}\ldots a_{n-1}\,$
$\displaystyle\sim\,-a|b:a_{1}a_{2}\ldots a_{n-1}\mbox{\ (edges);}$ (14)
$\displaystyle a|b:a_{1}a_{2}\ldots a_{n-1}\,$
$\displaystyle\rightarrow\,a|b+a_{1}:a_{2}a_{3}\ldots a_{n-1}\,aa_{1}\mbox{\
(arcs).}$ (15)

Notice that a vertex $a|x_{1}x_{2}\ldots x_{n}$ with the old presentation is
now labeled as $a|b:a_{1}\ldots a_{n-1}$ with $b=x_{1}$ and
$a_{i}=x_{i+1}-x_{i}$ for $i=1,\ldots,n-1$. From this, it is readily checked
that the ‘new’ adjacencies are as mentioned.

######  Proposition 2.3.

The group of automorphisms of $F^{*}(n)$ is isomorphic to the dihedral group
$D_{3}$.

###### Proof.

Using the new notation, let us first show that the following mappings, $\Phi$
and $\Psi$, are automorphisms of $F^{*}(n)$:

$\displaystyle\Phi(a|b:a_{1}a_{2}\ldots a_{n-1})$
$\displaystyle=a|\phi(b):\overline{a_{1}}\,\overline{a_{2}}\ldots\overline{a_{n-1}};$
(16) $\displaystyle\Psi(a|b:a_{1}a_{2}\ldots a_{n-1})$
$\displaystyle=a|b+1:a_{1}a_{2}\ldots a_{n-1},$ (17)

where $\phi(0)=1$, $\phi(1)=0$, $\phi(2)=2$, and $\overline{a_{i}}=-a_{i}$ for
$i=1,\ldots,n-1$. To prove that $\Phi$ is an automorphism of $F^{*}(n)$,
observe that the vertex in (16) is adjacent, through an edge, to

$\overline{a}|\phi(b):\overline{a_{1}}\,\overline{a_{2}}\ldots\overline{a_{n-1}}=\Phi(\overline{a}|b:a_{1}a_{2}\ldots
a_{n-1}),$

and, through an arc, to

$a|\phi(b)+\overline{a_{1}}:\overline{a_{2}}\ldots\overline{a_{n-1}}\,a\overline{a_{1}}=\Phi(a|b+a_{1}:a_{2}a_{3}\ldots
a_{n-1}\,aa_{1}),$

where the last equality holds since $\phi(b+a_{1})=\phi(b)+\overline{a_{1}}$,
and $a\overline{a_{1}}=\overline{aa_{1}}$ for every $b\in\mathbb{Z}_{3}$ and
$a,a_{1}\in\\{+1,-1\\}$. Similarly, we can prove that $\Psi$ is also an
automorphism of $F^{*}(n)$. Clearly, $\Phi$ is involutive, and $\Psi$ has
order three. Moreover, $(\Phi\Psi)^{2}=\operatorname{id}$ (the identity).
Then, the automorphism group $\operatorname{Aut}(F^{*}(n))$ must contain the
subgroup $\langle\Phi,\Psi\rangle=D_{3}$. It is easy to see that the graph
$F^{*}(n)$ has exactly three digons between pairs of vertices of the form
$-1:xyxy\ldots xy$ and $-1:yxyx\ldots yx$ when $n$ is even, or $+1:xyxy\ldots
x$ and $+1:yxyx\ldots y$ when $n$ is odd; see again Figure 4. Thus, any
automorphism of $F^{*}(n)$ must interchange these digons; hence, the
automorphism group has at most $3!=6$ elements. Consequently,
$\operatorname{Aut}(F^{*}(n))\cong D_{3}\cong S_{3}$, as claimed. ∎

Before giving the diameter of $F^{*}(n)$, we show that, for every vertex $u$,
there is only a possible vertex $v$ at distance $2n+1$ from $u$. Suppose first
that $n$ is even (the case of odd $n$ is similar). It is clear that, excepting
possibly one case, from vertex $\mbox{\boldmath$u$}=a|b:a_{1}a_{2}\ldots
a_{n-1}$ to vertex $\mbox{\boldmath$v$}=a^{\prime}|b^{\prime}:y_{1}y_{2}\ldots
y_{n-1}$, there is a path with at most $2n$ steps of the form
$-\rightarrow-\rightarrow\cdots-\rightarrow$, where ‘$-$’ stands for ‘$\sim$’
(edge) or ‘$\emptyset$’ (nothing), and ‘$\rightarrow$’ represents an arc. The
exception occurs when all the edges of the path are necessary. That is:

  * •

If $b^{\prime}=b+\Sigma+\overline{a}$ (where
$\Sigma=\textstyle\sum_{i=1}^{n-1}a_{i}$, and so that $b^{\prime}\neq
b+\Sigma$), then the first two steps are

$a|b:a_{1}a_{2}\ldots a_{n-1}\ \sim\ \overline{a}|b:a_{1}a_{2}\ldots a_{n-1}\
\rightarrow\ \overline{a}|b+a_{1}:a_{2}a_{3}\ldots
a_{n-1}\,\overline{a}a_{1}.$

  * •

If $y_{1}=aa_{2}$, then the next two steps are

$\displaystyle\overline{a}|b+a_{1}:a_{2}a_{3}\ldots
a_{n-1}\,\overline{a}a_{1}\ $ $\displaystyle\sim\ a|b+a_{1}:a_{2}a_{3}\ldots
a_{n-1}\,\overline{a}a_{1}\ $ $\displaystyle\rightarrow\
a|b+a_{1}+a_{2}:a_{3}\ldots a_{n-1}\,\overline{a}a_{1}\,aa_{2}.$

  * •

If $y_{1}=\overline{a}a_{3}$, then the next two steps are

$\displaystyle a|b+a_{1}+a_{2}:a_{3}\ldots a_{n-1}\,\overline{a}a_{1}\,aa_{2}\
$ $\displaystyle\sim\ \overline{a}|b+a_{1}+a_{2}:a_{3}\ldots
a_{n-1}\,\overline{a}a_{1}\,aa_{2}\ $ $\displaystyle\rightarrow\
\overline{a}|b+a_{1}+a_{2}+a_{3}:a_{4}\ldots
a_{n-1}\,\overline{a}a_{1}\,aa_{2}\,\overline{a}a_{3}.$

  * $\vdots$

  * •

If $y_{n-1}=a\overline{a}a_{1}=-a_{1}$, then the last two steps are

$\displaystyle\overline{a}|b+\Sigma:\overline{a}a_{1}\,aa_{2}\,\overline{a}a_{3}\ldots\overline{a}a_{n-1}\,$
$\displaystyle\sim\
a|b+\Sigma:\overline{a}a_{1}\,aa_{2}\ldots\overline{a}a_{n-1}\ $
$\displaystyle\rightarrow\
a|b+\Sigma+\overline{a}a_{1}:aa_{2}\ldots\overline{a}a_{n-1}\,\overline{a_{1}}$
$\displaystyle=a|b^{\prime}:y_{1}y_{2}\ldots y_{n-1}.$

Thus, if $a\neq a^{\prime}$ $(a^{\prime}=\overline{a})$, the vertex

$\mbox{\boldmath$v$}=\overline{a}|b+\Sigma+\overline{a}a_{1}:aa_{2}\,\overline{a}a_{3}\ldots\overline{a}a_{n-1}\,\overline{a_{1}}$

is not reached from $u$ in this way. Similarly, if $n$ is odd, the exception
is the vertex

$\mbox{\boldmath$v$}=a|b+\Sigma+\overline{a}a_{1}:aa_{2}\,\overline{a}a_{3}\ldots
aa_{n-1}\,\overline{a_{1}}.$

###  2.4 The mixed graphs $F^{\prime}(n)$

If necessary, the three digons of $F^{*}(n)$ can be removed and replaced by
three new edges of the form

$\displaystyle+1:xyxy\ldots xy$ $\displaystyle\ \sim\ +1:yxyx\ldots
yx\qquad\mbox{($n$ even)},$ $\displaystyle-1:xyxy\ldots yx$ $\displaystyle\
\sim\ -1:yxyx\ldots xy\qquad\mbox{($n$ odd)}.$

So, we obtain the new mixed graph $F^{\prime}(n)$, with $N=3\cdot 2^{n}-6$
vertices and diameter $k\leq 2n$. More precisely, $F^{\prime}(2)$ is
isomorphic to the Kautz digraph $K(2,2)$ with $N=6$ vertices and diameter
$k=2$; and when $n\in\\{3,4\\}$, the mixed graph $F^{\prime}(n)$ has diameter
$k=2n-1$. For instance, the mixed graph $F^{\prime}(4)$, with $N=42$ vertices
and diameter $k=7$, is shown in Figure 5. In all the other cases, when $n\geq
5$, computational results seem to show that the diameter of $F^{\prime}(n)$ is
always $k=2n$.

Figure 5: The mixed graph $F^{\prime}(4)$ with $42$ vertices and diameter $7$.

###  2.5 The mixed graphs $G(n)$

We define a $(1,1,k)$-regular mixed graph $G(n)$, for $n\geq 2$, as follows:
the vertices are of the form $x_{0}|x_{1}\ldots x_{n}$, where
$x_{i}\in\mathbb{Z}_{2}$ for $i=0,1,\ldots,n$. More precisely, the vertices
are:

  * $\circ$

For any $n$: $1|00\ldots 0$ and $1|11\ldots 1$;

  * $\circ$

For odd $n$: $0|0101\ldots 0$ and $0|1010\ldots 1$;

  * $\circ$

For even $n$: $1|0101\ldots 01$ and $1|1010\ldots 10$;

  * $\circ$

For the other vertices, $0|x_{1}\ldots x_{n}$ and $1|x_{1}\ldots x_{n}$, with
$x_{i}\in\mathbb{Z}_{2}$.

So, the number of vertices of $G(n)$ is $2^{n+1}-4$.
The adjacencies (with arithmetic modulo 2) through edges are:

  * $(i)$

For any $n$: $1|00\ldots 0\,\sim\,1|11\ldots 1$;

  * $(ii)$

For odd $n$: $1|0101\ldots 0\,\sim\,1|1010\ldots 1$;

  * $(iii)$

For even $n$: $0|0101\ldots 01\,\sim\,0|1010\ldots 10$;

  * $(iv)$

For the other vertices, $x_{0}|x_{1}\ldots x_{n}\,\sim\,(x_{0}+1)|x_{1}\ldots
x_{n}$.

The adjacencies through arcs are:

  * $(v)$

$x_{0}|x_{1}\ldots x_{n}$ $\rightarrow$ $x_{0}|x_{2}\ldots
x_{n}(x_{1}+x_{0})$.

The graph $G(n)$ is an in- and out-regular mixed graph with $r=z=1$. Its only
nontrivial automorphism is the one that sends
$x_{0}|\mbox{\boldmath$x$}=x_{0}|x_{1}x_{2}x_{3}\ldots$ to
$x_{0}|\overline{\mbox{\boldmath$x$}}=x_{0}|\overline{x_{1}}\,\overline{x_{2}}\,\overline{x_{3}}\ldots$,
where $\overline{x_{i}}=x_{i}+1$ for $i=1,2,3,\ldots$ In Figure 6, we show the
mixed graph $G(3)$.

Figure 6: The mixed graph $G(3)$.

Looking at the results for $n\leq 12$ obtained by computer, we are led to
conjecture that the diameter of $G(n)$ is $k=2n-1$. At first sight, the proof
of this result seems to be involved, although we managed to prove the
following.

######  Proposition 2.4.

The diameter of $G(n)$ is at most $2n$.

###### Proof.

Consider the digraph $G^{+}(n)$ defined by considering all $2^{n+1}$ vertices
of the form $0|x_{1}\ldots x_{n}$ and $1|x_{1}\ldots x_{n}$, with
$x_{i}\in\mathbb{Z}_{2}$, with undirected adjacencies as in $(iv)$, and
directed adjacencies as in $(v)$. Then, $G^{+}(n)$ has the self-loops at
vertices $0|00\ldots 0$ and $0|11\ldots 1$ and one digon (or two opposite
arcs) between $0|0101\ldots 01$ and $0|1010\ldots 10$ for even $n$, and
$0|0101\ldots 0$ and $0|1010\ldots 1$ for odd $n$. In fact, if every edge of
$G^{+}(n)$ is ‘contracted’ to a vertex, what remains is the De Bruijn digraph
$B(2,n)$, with $2^{n}$ vertices and diameter $n$. Moreover, notice that $G(n)$
is obtained by removing the above four vertices and adding the edges in $(i)$,
$(ii)$, and $(iii)$. By way of examples, Figure 7 shows the graph $G^{+}(2)$,
whereas Figure 8 shows the mixed graph $G^{+}(3)$ ‘hanging’ from a vertex with
eccentricity $2n=6$.

Consequently, since the diameter of $G(n)$ is upper bounded by the diameter of
$G^{+}(n)$, we concentrate on proving that the diameter of $G^{+}(n)$ is $2n$
for $n>1$ ($G(1)$ has diameter $3$). The proof is constructive because we show
a walk of length at most $2n$ between any pair of vertices. To this end, we
take the following steps:

  1. 1.

There is a walk of length at most $2n$ from vertex
$x_{0}|\mbox{\boldmath$x$}=x_{0}|x_{1}x_{2}\ldots x_{n}$ to vertex
$(x_{n}+y_{n})|y_{1}y_{2}\ldots y_{n}$. Indeed, as $x_{i}+x_{i}=0$ for any
value of $x_{i}$, we get

$\displaystyle x_{0}|x_{1}x_{2}x_{3}\ldots x_{n}$
$\displaystyle\,\sim\,(x_{1}+y_{1})|x_{1}x_{2}x_{3}\ldots
x_{n}\rightarrow(x_{1}+y_{1})|x_{2}x_{3}\ldots x_{n}y_{1}$
$\displaystyle\,\sim\,(x_{2}+y_{2})|x_{2}x_{3}\ldots
x_{n}y_{1}\rightarrow(x_{2}+y_{2})|x_{3}\ldots x_{n}y_{1}y_{2}$
$\displaystyle\ \vdots$ (18)
$\displaystyle\,\sim\,(x_{n}+y_{n})|x_{n}y_{1}y_{2}y_{3}\ldots
y_{n-1}\rightarrow(x_{n}+y_{n})|y_{1}y_{2}\ldots y_{n}.$

Thus, the initial vertex $x_{0}|x$ and the step pattern
‘$\sim\rightarrow\sim\rightarrow\stackrel{{\scriptstyle(2n)}}{{\cdots\cdots}}\sim\rightarrow$’
uniquely determine the destiny vertex.

Figure 7: The graph $G^{+}(2)$. Figure 8: The graph $G^{+}(3)$ ‘hanging’ from
vertex $0|101$, with eccentricity $6$.

  2. 2.

Clearly, some of the steps in (18) are not necessary if some of the following
situations occur:

    1. (a)

The ‘intersection’ of the sequences $\mbox{\boldmath$x$}=x_{1}x_{2}\ldots
x_{n}$ and $\mbox{\boldmath$y$}=y_{1}y_{2}\ldots y_{n}$ (that is, the maximum
length of the last subsequence of $x$ that coincides with a first subsequence
of $y$), denoted $|\mbox{\boldmath$x$}\cap\mbox{\boldmath$y$}|$, is greater
than zero. (For instance, for $\mbox{\boldmath$x$}=0\ldots 010$ and
$\mbox{\boldmath$y$}=100\ldots 0$, we get
$|\mbox{\boldmath$x$}\cap\mbox{\boldmath$y$}|=2$.) In this case, the first
$\ell=|\mbox{\boldmath$x$}\cap\mbox{\boldmath$y$}|$ step pairs
‘$\sim\rightarrow$’ of the walk in (18) are useless and can be avoided. Then,
we say that we save $2\ell$ steps.

    2. (b)

Some of the following equalities hold: $x_{0}=x_{1}+y_{1}$, or
$x_{i}+y_{i}=x_{i+1}+y_{i+1}$ for some $i=1,\ldots,n-1$. In this case, some
steps ‘$\sim$’ are absent. More precisely, if either both equalities
$x_{i}=y_{i}$ and $x_{i+1}=y_{i+1}$ (or both inequalities $x_{i}\neq y_{i}$
and $x_{i+1}\neq y_{i+1}$) hold, then the step ‘$\sim$’ through an edge
leading to $(x_{i+1}+y_{i+1})|x_{i+1}\ldots x_{n}y_{1}\ldots y_{i}\ldots$ is
absent. So, we save $1$ step.

Thus, if we can save some steps, one last step
$(x_{n}+y_{n})|\mbox{\boldmath$y$}\sim(\overline{x_{n}+y_{n}})|\mbox{\boldmath$y$}$
assures a walk of length at most $2n$ from $x_{0}|\mbox{\boldmath$x$}$ to
$y_{0}|\mbox{\boldmath$y$}$ for any $y_{0}\in\\{0,1\\}$.

  3. 3.

In the ‘worst case’, the walk in (18) consists of exactly $2n$ steps (vertices
at maximum distance) if $|\mbox{\boldmath$x$}\cap\mbox{\boldmath$y$}|=0$ and
none of the equalities in (b) holds. Assuming first that $x_{0}=0$ (the case
$x_{0}=1$ is similar), the latter occurs when $x_{1}+y_{1}=1\Rightarrow
y_{1}=\overline{x_{1}}$, $x_{2}+y_{2}=0\Rightarrow y_{2}=x_{2}$,
$x_{3}+y_{3}=1\Rightarrow y_{3}=\overline{x_{3}}$, and so on. Consequently,
starting from $0|\mbox{\boldmath$x$}=0|x_{1}x_{2}x_{3}\ldots x_{n}$, we only
need to test the destiny vertices of the form
$1|\mbox{\boldmath$y$}=1|\overline{x_{1}}x_{2}\overline{x_{3}}\ldots x_{n}$
($n$ even), and $0|\mbox{\boldmath$z$}=$
$0|\overline{x_{1}}x_{2}\overline{x_{3}}\ldots\overline{x_{n}}$ ($n$ odd),
with the additional constraints
$|\mbox{\boldmath$x$}\cap\mbox{\boldmath$y$}|=|\mbox{\boldmath$x$}\cap\mbox{\boldmath$z$}|=0$.

  4. 4.

For these cases, the strategy is to put first the last digit of destiny.
Namely, if $n$ is even,

$\displaystyle 0|x_{1}x_{2}x_{3}\ldots x_{n}$ $\displaystyle\,\rightarrow
0|x_{2}x_{3}\ldots x_{n}x_{1}$
$\displaystyle\,\sim\,(x_{2}+\overline{x_{1}})|x_{2}x_{3}\ldots
x_{n}x_{1}\rightarrow(x_{2}+\overline{x_{1}})|x_{3}x_{4}\ldots
x_{n}x_{1}\overline{x_{1}}\,$
$\displaystyle\,\sim\,(x_{3}+x_{2})|x_{3}x_{4}\ldots
x_{n}x_{1}\overline{x_{1}}\,\rightarrow(x_{3}+x_{2})|x_{4}x_{5}\ldots
x_{n}x_{1}\overline{x_{1}}\,x_{2}$
$\displaystyle\,\sim\,(x_{4}+\overline{x_{3}})|x_{4}x_{5}\ldots
x_{n}x_{1}\overline{x_{1}}\,x_{2}\rightarrow(x_{4}+\overline{x_{3}})|x_{5}\ldots
x_{n}x_{1}\overline{x_{1}}\,x_{2}\overline{x_{3}}$ $\displaystyle\ \vdots$
(19)
$\displaystyle\,\sim\,(x_{n}+\overline{x_{n-1}})|x_{n}x_{1}\overline{x_{1}}x_{2}\ldots\overline{x_{n-1}}x_{n-2}\,$
$\displaystyle\,\rightarrow\,(x_{n}+\overline{x_{n-1}})|x_{1}\overline{x_{1}}x_{2}\ldots
x_{n-2}\overline{x_{n-1}}$
$\displaystyle\,\sim\,(x_{1}+x_{n})|x_{1}\overline{x_{1}}x_{2}\ldots
x_{n-2}\overline{x_{n-1}}\,\rightarrow(x_{1}+x_{n})|\overline{x_{1}}x_{2}\overline{x_{3}}\ldots
x_{n}$
$\displaystyle\,\sim\,1|(x_{1}+x_{n})|\overline{x_{1}}x_{2}\overline{x_{3}}\ldots
x_{n}.$

This walk can have $2n+2$ steps whenever all steps ‘$\sim$’ through edges are
present. This is the case when $x_{2}+\overline{x_{1}}\neq 0$,
$x_{3}+x_{2}\neq x_{2}+\overline{x_{1}}$, $x_{4}+\overline{x_{3}}\neq
x_{3}+x_{2}$,…, $x_{1}+x_{n}\neq x_{n}+\overline{x_{n-1}}$, and
$x_{1}+x_{n}\neq 1$. In turn, this implies the $n+1$ equalities

$\displaystyle x_{1}$ $\displaystyle=x_{3},\ x_{3}=x_{5},\ \ldots,\
x_{n-3}=x_{n-1},\ x_{n-1}=x_{1},$ (20) $\displaystyle x_{1}$
$\displaystyle=x_{2},\ x_{2}=x_{4},\ x_{4}=x_{6},\ \ldots,\ x_{n-2}=x_{n},\
x_{n}=x_{1}.$ (21)

Note that these sequences of equalities form two cycles (with odd and even
subscripts) rooted at $x_{1}$. Thus, the number of inequalities, if any, must
be at least $2$. In this case, at least $2$ steps ‘$\sim$’ are absent in (19),
and we have a walk of length at most $2n$ between the vertices considered.
Otherwise, if all the equalities (20)–(21) hold, the initial vertex must be
$0|000\stackrel{{\scriptstyle(n)}}{{\ldots}}00$ (the first digit $x_{1}$ can
be fixed to $0$ since the mixed graph has an automorphism that sends
$x_{0}|x_{1}x_{2}\ldots x_{n}$ to
$x_{0}|\overline{x_{1}}\,\overline{x_{2}}\,\ldots\overline{x_{n}}$), and the
destiny vertex is $0|1010\stackrel{{\scriptstyle(n)}}{{\ldots}}10$. The same
reasoning for $n$ odd leads that, in the worst case (walk in (19) of length
$2n+2$), the initial vertex is $0|000\ldots 0$ and the final vertex
$0|1010\ldots 1$. In such cases, we have a particular walk of the desired
length.

  5. 5.

There is a walk of length $2n$ from $0|000\ldots 0$ to $1|1010\ldots 10$ ($n$
even) or to $0|1010\ldots 01$ ($n$ odd) by using the following step pattern

$\sim\,\rightarrow\,\rightarrow\sim\,\rightarrow\,\sim\,\rightarrow\,\stackrel{{\scriptstyle(2n)}}{{\cdots\cdots}}\sim\,\rightarrow\,\rightarrow.$

For instance, for $n=6$, we get

$\displaystyle 0|000000$ $\displaystyle\,\sim\,1|000000\rightarrow
1|000001\rightarrow 1|000011$ $\displaystyle\,\sim\,0|000011\rightarrow
0|000110$ $\displaystyle\,\sim\,1|000110\rightarrow 1|001101$
$\displaystyle\,\sim\,0|001101\rightarrow 0|011010$
$\displaystyle\,\sim\,1|011010\rightarrow 1|110101\rightarrow 1|101010,$

and, for $n=7$,

$\displaystyle 0|0000000$ $\displaystyle\,\sim\,1|0000000\rightarrow
1|0000001\rightarrow 1|0000011$ $\displaystyle\,\sim\,0|0000011\rightarrow
0|0000110$ $\displaystyle\,\sim\,1|0000110\rightarrow 1|0001101$
$\displaystyle\,\sim\,0|0001101\rightarrow 0|0011010$
$\displaystyle\,\sim\,1|0011010\rightarrow 1|0110101$
$\displaystyle\,\sim\,0|0110101\rightarrow 0|1101010\rightarrow 0|1010101.$

  6. 6.

The case $x=1$ is similar, and we only mention the main facts. Now, the ‘worst
case’ ($2n$ steps) in the walk in (18) ($2n$ steps) occurs when, starting from
$1|\mbox{\boldmath$x$}=1|x_{1}x_{2}x_{3}\ldots x_{n}$, we want to reach the
destiny vertices of the form
$0|\mbox{\boldmath$y$}=0|x_{1}\overline{x_{2}}x_{3}\overline{x_{4}}\ldots\overline{x_{n}}$
($n$ even), or
$1|\mbox{\boldmath$z$}=1|x_{1}\overline{x_{2}}x_{3}\overline{x_{4}}\ldots
x_{n}$ ($n$ odd), with the additional constraints
$|\mbox{\boldmath$x$}\cap\mbox{\boldmath$y$}|=|\mbox{\boldmath$x$}\cap\mbox{\boldmath$z$}|=0$.
Now, following the same strategy as in step 4 above, it turns out that for the
case of $2n+2$ steps, the following conditions must hold (assuming $n$ odd,
the even case is similar):

$\displaystyle x_{1}$ $\displaystyle=x_{2},\ x_{2}=x_{3},\ \ldots,\
x_{n-1}=x_{n},\ x_{n}\neq x_{1},$ (22)

which are clearly incompatible, and at least there must be another inequality
(the last one in (22) is forced since the final vertex has $x_{0}=1$). Again,
at least $2$ steps ‘$\sim$’ are absent in (19), and we have a walk of length
at most $2n$ between the vertices considered. For example, for $n=5$, and
assuming that $x_{4}\neq x_{5}$ and $x_{1}=0$, the walk of $10$ steps from
$1|00001$ to $1|01011$ is:

$\displaystyle 1|00001$ $\displaystyle\,\rightarrow\,1|00011$
$\displaystyle\,\sim\,0|00011\rightarrow 0|00110$
$\displaystyle\,\sim\,1|00110\rightarrow 1|01101$
$\displaystyle\,\sim\,0|01101\rightarrow 0|11010$
$\displaystyle\,\rightarrow\,0|10101\rightarrow 0|01011\sim 1|01011.$

This completes the proof. ∎

In fact, we implicitly proved the following.

######  Lemma 2.5.

For every $n>1$, the mixed graph $G^{+}(n)$ satisfies the following.

  * $(i)$

The vertices $0|00\ldots 0$ and $0|11\ldots 1$ have maximum eccentricity $2n$.

  * $(ii)$

The vertices $1|00\ldots 0$ and $1|11\ldots 1$ have eccentricity $2n-1$.

  * $(iii)$

If $n\geq 5$, the vertices $1|00\ldots 01$ and $1|11\ldots 10$ have
eccentricity $2n-2$.

###### Proof.

$(i)$ and $(ii)$ follow from the previous reasoning. To prove $(iii)$, we only
need to check the distance from $1|00\ldots 01$ to $0|00\ldots 0$. A shortest
path between these two vertices is $1|00\ldots 01\sim 0|00\ldots 01\rightarrow
0|0\ldots 010\rightarrow\cdots\rightarrow 0|10\ldots 00\sim 1|10\ldots
00\rightarrow 1|00\ldots 00\sim 0|00\ldots 0$ of length $n+3\leq 2n-2$ if
$n\geq 5$. ∎

Let $\Psi_{0}$ and $\Psi_{1}$ be the functions that map a vertex
$x|\mbox{\boldmath$x$}$ to its adjacent vertex from an edge or an arc,
respectively. That is,

$\displaystyle\Psi_{0}(x_{0}|x_{1}x_{2}\ldots x_{n})$
$\displaystyle=\overline{x_{0}}|x_{1}x_{2}\ldots x_{n},$
$\displaystyle\Psi_{1}(x_{0}|x_{1}x_{2}\ldots x_{n})$
$\displaystyle=x_{0}|x_{1}x_{2}\ldots(x_{0}+x_{1}).$

Let $\Phi=(\phi_{1},\phi_{2},\ldots,\phi_{n})$ be the function that maps every
$x_{i}$ to either $x_{i}$ or $\overline{x_{i}}$, for $i=1,2,\ldots,n$.

######  Lemma 2.6.

For any fixed functions $\Psi_{j}$ and $\Phi$, and first digit $x_{0}=0,1$, we
have

$\Psi_{j}(x_{0}|\Phi(\mbox{\boldmath$x$}))=\Phi(\Psi_{j}(x_{0}|\mbox{\boldmath$x$})),$

where $\Phi$ only acts on the digits $x_{1},x_{2},\ldots,x_{n}$.

###### Proof.

$\displaystyle\Psi_{0}(x_{0}|\Phi(\mbox{\boldmath$x$}))$
$\displaystyle=\Psi_{0}(x_{0}|\phi_{1}(x_{1})\phi_{2}(x_{2})\ldots\phi_{n}(x_{n}))=\overline{x_{0}}|\phi_{1}(x_{1})\phi_{2}(x_{2})\ldots\phi_{n}(x_{n})$
$\displaystyle=\Phi(\Psi_{0}(x_{0}|\mbox{\boldmath$x$})).$
$\displaystyle\Psi_{1}(x_{0}|\Phi(\mbox{\boldmath$x$}))$
$\displaystyle=\Psi_{1}(x_{0}|\phi_{1}(x_{1})\phi_{2}(x_{2})\ldots\phi_{n}(x_{n}))=x_{0}|\phi_{2}(x_{2})\ldots\phi_{n}(x_{n})(x_{0}\phi_{1}(x_{1}))$
$\displaystyle=\Phi(\Psi_{1}(x_{0}|\mbox{\boldmath$x$})).$

∎

Another property of the mixed graph $G^{+}(n)$ for $n>1$ is that from every
pair of (not necessarily distinct) vertices $u$ and $v$, there is at least a
walk of length $2n$ from $u$ to $v$. For instance, for $n=2$, fixing as before
$x_{1}=0$ and setting $y=x_{0}+x_{2}$, we have the following walks of length
$4$ from $x_{0}|0x_{2}$ to every vertex of $G^{+}(2)$.

$\displaystyle x_{0}|0x_{2}$
$\displaystyle\,\sim\,\overline{x_{0}}|0x_{2}\,\sim\,x_{0}|0x_{2}\,\rightarrow\,x_{0}|x_{2}x_{0}\,\rightarrow\,x_{0}|x_{0}(x_{0}+x_{2})$
$\displaystyle=x_{0}|x_{0}y$
$\displaystyle\,\rightarrow\,x_{0}|x_{2}x_{0}\,\sim\,\overline{x_{0}}|x_{2}x_{0}\,\rightarrow\,\overline{x_{0}}|x_{0}(\overline{x_{0}}+x_{2})\sim\,x_{0}|x_{0}(\overline{x_{0}}+x_{2})$
$\displaystyle=x_{0}|x_{0}\overline{y}$
$\displaystyle\,\sim\,\overline{x_{0}}|0x_{2}\,\rightarrow\,\overline{x_{0}}|x_{2}\overline{x_{0}}\,\sim\,x_{0}|x_{2}\overline{x_{0}}\,\rightarrow\,x_{0}|\overline{x_{0}}(x_{0}+x_{2})$
$\displaystyle=x_{0}|\overline{x_{0}}y$
$\displaystyle\,\sim\,\overline{x_{0}}|0x_{2}\,\rightarrow\,\overline{x_{0}}|x_{2}\overline{x_{0}}\,\rightarrow\,\overline{x_{0}}|\overline{x_{0}}(\overline{x_{0}}+x_{2})\,\sim\,x_{0}|\overline{x_{0}}(\overline{x_{0}}+x_{2})$
$\displaystyle=x_{0}|\overline{x_{0}}\overline{y}$
$\displaystyle\,\rightarrow\,x_{0}|x_{2}x_{0}\,\rightarrow\,x_{0}|x_{0}(x_{0}+x_{2})\,\rightarrow\,x_{0}|(x_{0}+x_{2})0\,\sim\,\overline{x_{0}}|(x_{0}+x_{2})0$
$\displaystyle=\overline{x_{0}}|y0$
$\displaystyle\,\rightarrow\,x_{0}|x_{2}x_{0}\,\rightarrow\,x_{0}|x_{0}(x_{0}+x_{2})\,\sim\,\overline{x_{0}}|(x_{0}+x_{2})\,\rightarrow\,\overline{x_{0}}|(x_{0}+x_{2})1$
$\displaystyle=\overline{x_{0}}|y1$
$\displaystyle\,\sim\,\overline{x_{0}}|0x_{2}\,\rightarrow\,\overline{x_{0}}|x_{2}\overline{x_{0}}\,\rightarrow\,\overline{x_{0}}|\overline{x_{0}}(\overline{x_{0}}+x_{2})\,\rightarrow\,\overline{x_{0}}|(\overline{x_{0}}+x_{2})0$
$\displaystyle=\overline{x_{0}}|\overline{y}0$
$\displaystyle\,\rightarrow\,x_{0}|x_{2}x_{0}\,\sim\,\overline{x_{0}}|x_{2}x_{0}\,\rightarrow\,\overline{x_{0}}|x_{0}(\overline{x_{0}}+x_{2})0\,\rightarrow\,\overline{x_{0}}|(\overline{x_{0}}+x_{2})1$
$\displaystyle=\overline{x_{0}}|\overline{y}1.$

Working with the adjacency matrix $A$ of $G^{+}(2)$ (indexed according to
Figure 7), the above property is apparent when we look at the power
$\mbox{\boldmath$A$}^{4}$.

$A$ $\displaystyle=\left(\begin{array}[]{cccccccc}1&1&0&0&0&0&0&0\\\
1&0&1&0&0&0&0&0\\\ 0&0&0&1&0&0&1&0\\\ 0&0&1&0&1&0&0&0\\\ 0&0&0&1&0&1&0&0\\\
0&1&0&0&1&0&0&0\\\ 0&0&0&0&0&1&0&1\\\ 0&0&0&0&0&0&1&1\end{array}\right),$
$\displaystyle\mbox{\boldmath$A$}^{4}=\left(\begin{array}[]{cccccccc}5&3&3&1&1&1&1&1\\\
3&3&1&3&1&1&3&1\\\ 1&1&3&1&3&3&1&3\\\ 1&1&1&5&1&3&3&1\\\ 1&3&3&1&5&1&1&1\\\
3&1&3&3&1&3&1&1\\\ 1&3&1&1&3&1&3&3\\\ 1&1&1&1&1&3&3&5\\\ \end{array}\right).$

###  2.6 The $n$-line mixed graphs

Let $G=(V,A)$ be a $2$-regular digraph with a given $1$-factorization, that
is, containing two arc-disjoint spanning $1$-regular digraphs $H_{1}$ and
$H_{2}$. Assuming that the arcs of $H_{1}$ have color blue and the arcs of
$H_{2}$ have color red, we can also think about a (proper) arc-coloring
$\gamma$ of $G$. Then, if $xy$ represents an arc of $G$, we denote its color
as $\gamma(xy)$.
Given an integer $n\geq 3$, the vertices of the $n$-line mixed graph
$H(n)=H_{n}(G)$ are the set of $n$-walks in $G$, $x_{1}x_{2}\ldots
x_{n-1}x_{n}$, with $x_{i}\in V$ and $x_{i}x_{i+1}\in A$, for
$i=1,\ldots,n-1$. The adjacencies of $H(n)$ are as follows:

$\displaystyle x_{1}x_{2}\ldots x_{n-1}x_{n}$ $\displaystyle\sim\
y_{1}x_{2}\ldots x_{n-1}x_{n}\mbox{\ (edges),}$ (23)

where $\gamma(y_{1}x_{2})\neq\gamma(x_{1}x_{2})$; and

$\displaystyle x_{1}x_{2}\ldots x_{n-1}x_{n}$ $\displaystyle\rightarrow\
x_{2}\ldots x_{n-1}x_{n}y_{n+1}\mbox{\ (arcs),}$ (24)

where $\gamma(x_{n}y_{n+1})\\!=$red if
$\gamma(x_{1}x_{2})=\gamma(x_{n-1}x_{n})$, and $\gamma(x_{n}y_{n+1})\\!=$blue
if $\gamma(x_{1}x_{2})\neq\gamma(x_{n-1}x_{n})$. The reason for the name of
$H_{n}(G)$ is because when we contract all its edges, so identifying the
vertices in (23), the resulting digraph is the $(n-1)$-iterated line digraph
$L^{n-1}(G)$ of $G$, see Fiol, Yebra, and Alegre [15]. Indeed, under such an
operation, each pair of vertices in (23) becomes a vertex that can be
represented by the sequence $x_{2}x_{3}\ldots x_{n}$, which, according to
(24), is adjacent to the two vertices $x_{3}\ldots x_{n}y_{n+1}$ with
$y_{n+1}\in\Gamma^{+}(x_{n})$ in $G$.
In the following result, we describe other basic properties of $H_{n}(G)$.

######  Proposition 2.7.

Let $G=(V,A)$ be a digraph with $r$ vertices and diameter $s$, having a
$1$-factorization. For a given $n\geq 3$, the following holds.

  * $(i)$

The mixed graph $H_{n}=H_{n}(G)$ has $N=r\cdot 2^{n-1}$ vertices, and it is
totally $(1,1)$-regular with no digons.

  * $(ii)$

The diameter of $H_{n}$ satisfies $k\leq 2(s+n)-3$.

###### Proof.

$(i)$ Every vertex $x_{1}\ldots x_{n}$ of $H_{n}$ corresponds to a walk of $G$
with first vertex $x_{1}$, which gives $r$ possibilities and, since $G$ is
$2$-regular, for every other $x_{i}$, $i=2,\ldots,n$, we have $2$ possible
options. This provides the value of $N$.
To show total $(1,1)$ regularity, it is enough to prove that $H_{n}$ is
$1$-in-regular. Indeed, any vertex adjacent to $x_{1}x_{2}\ldots x_{n}$, with
$\gamma(x_{n-1}x_{n})$=blue (respectively, $\gamma(x_{n-1}x_{n})=$ red) must
be of the form $yx_{1}\ldots x_{n-2}x_{n-1}$ with
$\gamma(yx_{1})\neq\gamma(x_{n-2}x_{n-1})$ (respectively, with
$\gamma(yx_{1})=\gamma(x_{n-2}x_{n-1}))$. But, in both cases, there is only
one possible choice for vertex $y$.
With respect to the absence of digons, notice that a vertex
$\mbox{\boldmath$u$}=x_{1}x_{2}\ldots x_{n-1}x_{n}$ belongs to a digon if,
after two steps, we come back to $u$, which means that $x_{1}x_{2}\ldots
x_{n-1}x_{n}=x_{3}x_{4}\ldots x_{n}y_{n+1}y_{n+2}$ and, hence,
$x_{i}=x_{3}=\cdots$ and $x_{2}=x_{4}=\cdots$. In other words, vertex $u$ must
be of the form $xyxy\cdots xy$ ($n$ even) or $xyxy\cdots x$ ($n$ odd), and $G$
itself must have a digon between vertices $x$ and $y$. Assuming that $n$ is
even and $\gamma(xy)$=blue (the other cases are similar), the digon should be

$\mbox{\boldmath$u$}=xyxy\ldots
xy\quad\rightarrow\quad\mbox{\boldmath$v$}=yxyx\ldots
yx\quad\rightarrow\quad\mbox{\boldmath$u$}.$

But the last adjacency is not possible since both the first and last arcs of
$v$ would have color $\gamma(yx)=$red and, hence, so should be the color of
$xy$, a contradiction.
$(ii)$ Given both vertices $x_{1}x_{2}\ldots x_{n-1}x_{n}$ and
$y_{1}y_{2}\ldots y_{n-1}y_{n}$, let us consider a shortest path in $G$ of
length at most $s$ from $x_{n}$ to $y_{2}$. Then, using both types of
adjacencies, we can go from $x_{1}x_{2}\ldots x_{n-1}x_{n}$ to a vertex of the
form $z_{1}\ldots y_{2}$. From this vertex, we now reach the vertex
$yy_{2}\ldots y_{n}$ in at most $2(n-2)$ steps. Finally, if necessary, we can
change $y$ by $y_{1}$. In total, we use $k\leq 2s+2(n-2)+1=2(s+n)-3$ steps, as
claimed. ∎

For example, if $G$ is the complete symmetric digraph $K_{3}$ (edges seen as
digons) with vertices in $\mathbb{Z}_{3}$, blue arcs $i\rightarrow i+1$ and
red arcs $i\rightarrow i-1$ for $i=0,1,2$, the adjacencies of $H_{n}(K_{3})$,
with $3\cdot 2^{n-1}$ vertices, are

$\displaystyle x_{1}x_{2}\ldots x_{n-1}x_{n}$ $\displaystyle\sim\
y_{1}x_{2}\ldots x_{n-1}x_{n},\quad y_{1}\neq x_{1},x_{2},$ $\displaystyle
x_{1}x_{2}\ldots x_{n-1}x_{n}$ $\displaystyle\rightarrow\ x_{2}x_{3}\ldots
x_{n}y_{n+1},\quad y_{n+1}=x_{n}-(x_{2}-x_{1})(x_{n}-x_{n-1}).$

Thus, the $(1,1)$-regular mixed graphs $H_{3}(K_{3})$ and $H_{4}(K_{3})$, with
diameter $k=5$ and $k=6$, respectively, are shown in Figure 9.

Figure 9: The mixed graphs $H_{3}(K_{3})$ and $H_{4}(K_{3})$.

In this case, when we contract all the edges of $H_{n}(K_{3})$, we obtain the
$(n-1)$-iterated line digraph of $K_{3}$, which, as commented in Introduction,
is isomorphic to the Kautz digraph $K(2,n-1)$.

##  3 A first computational approach: The $(1,1,k)$-mixed graphs with diameter
at most 6

The Moore bound $M(1,1,k)$ coincides with the number of binary words of length
$\ell\leq k$ without consecutive zeroes. In this sense, the corresponding
Moore tree can be rooted to a vertex labeled with the empty word. Every vertex
labeled with a word $\omega$ (of length $\ell$) with the last symbol different
from 0 is joined by an edge to a vertex labeled $\omega 0$ (of length
$\ell+1$), for all $0\leq\ell\leq k-1$. Moreover, the arcs are defined by
$\omega\rightarrow\omega 1$ (see an example in Figure 10).

This new description of the Moore tree is very useful for performing an
exhaustive computational search of the largest mixed graphs for some small
values of the diameter $k$. Let $a(\ell)$ be the number of vertices at
distance $\ell$ from the root in the Moore tree. Using the above-mentioned
labeling, it is easy to see that $a(\ell)$ satisfies the recurrence equation

$a(\ell)=a(\ell-1)+a(\ell-2),$ (25)

with initial conditions $a(0)=1$ and $a(1)=2$. Indeed, $a(\ell)$ is the number
of words of length $\ell$ (whose symbols are in the alphabet
$\Sigma=\\{0,1\\}$) without consecutive zeroes. The words of length $\ell$
non-ending with 0 are constructed by a word of length $\ell-1$ by adding $0$.
This gives $a(\ell-1)$. Moreover, the words of length $\ell$ ending with $0$
are constructed by adding $1$. This gives $a(\ell-2)=b(\ell)$, where $b(\ell)$
is the number of vertices at distance $\ell$ from the root joined by an edge
to a vertex at distance $\ell-1$. So $b(\ell)$ satisfies the same recurrence
relation as $a(\ell)$ but with initial conditions $b(0)=0$ and $b(1)=1$.
Finally, let $c(\ell)=a(\ell)-b(\ell)=a(\ell-1)$, that is, the number of
vertices at distance $\ell$ from the root pointed by an arc from a vertex at
distance $\ell-1$. Again, $c(\ell)$ satisfies the same type of recurrence
relation but with initial conditions $c(0)=1$ and $c(1)=1$. Thus, $a(\ell)$,
$b(\ell)$, and $c(\ell)$ are all Fibonnaci-like numbers. For instance,
$a(\ell)$ equals the following closed formula

$a(\ell)=\frac{5+3\sqrt{5}}{10}\left(\frac{1+\sqrt{5}}{2}\right)^{\ell}+\frac{5-3\sqrt{5}}{10}\left(\frac{1-\sqrt{5}}{2}\right)^{\ell}.$

Note that the sequence obtained from $a(\ell)$ corresponds to the Fibonacci
numbers starting with $a(0)=1$ and $a(1)=2$ (see the sequence A000045 in
[25]). Similar formulas can be obtained for $b(\ell)$ and $c(\ell)$.

Now, we can perform an algorithmic exhaustive search to find all the largest
$(1,1,k)$-mixed graphs with order close to the Moore bound. For instance, in
the case of almost mixed Moore graphs (with diameter $k$ and order
$M(1,1,k)-1$), the number of different cases of mixed graphs to analyze is
bounded by ${\cal N}(k)$, where ${\cal N}(k)$ is computed next.

  1. 1.

We remove a vertex in the Moore tree at distance $k$ from the empty word.
Notice there are $a(k)$ different choices for this vertex.

  2. 2.

Now, we count the number ${\cal N}_{1}$ of possibilities to complete the
undirected part of the mixed graph. We recall that the number of perfect
matchings in a complete graph of even order $n$ is $(n-1)!!$ This number
${\cal N}_{1}$ depends on what vertex has been removed in the previous step.
If the removed vertex has a label ending with $0$, that is, it is a vertex
hanging from an edge, then there are $c(k)+1$ vertices in the graph without an
incident edge. So, ${\cal N}_{1}=c(k)!!$ Otherwise, there are $c(k)-1$
vertices in the graph without an incident edge, so ${\cal N}_{1}=(c(k)-2)!!$

  3. 3.

The number of possibilities to complete the directed part of the graph is
upper bounded by the number of mappings from the set of words of length $k$
without fixing points. This is precisely the number of derangements
$D_{a(k)}$. Notice that mappings, including assignations from a word of length
$k$ to its predecessor, are not valid.

Figure 10: The Moore tree with parameters $r=z=1$ and depth $4$ labeled with
binary words without consecutive zeros.

Putting all together, ${\cal
N}(k)<D_{a(k)}\left(b(k)c(k)!!+c(k)(c(k)-2)!!\right)$. Of course, ${\cal
N}(k)$ grows very fast with $k$ but the number of cases to analyze for $k\leq
4$ is reasonable (see Table 1).

$k$ | $3$ | $4$ | $5$ | $6$
---|---|---|---|---
$N(k)$ | $396$ | $889980$ | $0$ | $2\cdot 10^{25}$
Table 1: Values of ${\cal N}(k)$. Notice that ${\cal N}(5)=0$ because $c(5)$
is an even number.

As a consequence, computing the diameter of the $889980$ putative almost Moore
$(1,1)$-mixed graphs with diameter $k=4$, we have the following result. (In
fact, this calculation is easily done by using the result by Tuite and
Erskhine [27] that such graphs are not totally regular.)

######  Proposition 3.1.

There is no almost $(1,1,4)$-mixed Moore graph.

A similar method can be implemented to perform an exhaustive search for orders
$M(1,1,k)-\delta$ for small $\delta$. In these cases, the removal of $\delta$
different vertices of the Moore tree (step 1) has many more choices but the
number of operations in steps 2 and 3 sometimes is reduced. This is precisely
what we do for $n=M(1,1,4)-3=16$, where there are two cases to take into
account:

  * •

The removal of three distinct words $\omega_{1},\omega_{2},\omega_{3}$ of
length $4$ (corresponding to three distinct vertices at distance $4$ from the
root of the Moore tree).

  * •

Given any word $\omega$ of length $3$, the deletion of either the set of words
$\\{\omega,\omega 1,\omega^{\prime}\\}$ (when $\omega$ ends in $0$) or
$\\{\omega,\omega 0,\omega 1\\}$ (when $\omega$ ends in $1$), where
$\omega^{\prime}\neq\omega 1$ is any word of length $4$.

It remains to add the corresponding edges and arcs in the pruned Moore tree.
The computational exhaustive search shows there is no $(1,1)$-mixed Moore
graph of diameter $4$ and order $16$. Now the maximum order becomes $n=14$ for
a mixed graph with parameters $r=z=1$ and $k=4$. There are many more
possibilities to prune the Moore tree, so we decide to implement a direct
method to perform an exhaustive search in this case: taking the perfect
matching with a set of vertices $V=\\{0,1,\dots,13\\}$ and where $i\sim i+1$
for all even $i$, we add the three arcs $(0,2),(1,5)$ and $(5,7)$. Looking at
vertex $0$ as the root of the Moore tree, the existence of these three arcs in
the mixed graph is given because $\delta=5$ in this case. Now we proceed with
the exhaustive search by adding the remaining arcs in the graph. There are
$11!$ possibilities but excluding avoided permutations (those permutations
with elements of order at most $2$ or including edges of the perfect matching)
significantly reduces the number of cases to analyze. After computing the
diameter of all these mixed graphs and keeping those non-isomorphic mixed
graphs with diameter $k=4$, we have the following result.

######  Proposition 3.2.

The maximum order for a $(1,1)$-mixed regular graph of diameter $k=4$ is $14$.
There are $27$ of such mixed graphs (see Table 2), and only one of them is a
Cayley graph. Namely, that of the dihedral group $D_{7}$ with generators $r$
and $s$, and presentation $\langle
r,s\,|\,r^{7}\\!=\\!s^{2}\\!=\\!(rs)^{2}\\!=\\!1\rangle$, also obtained as the
line digraph of $C_{7}$, see the mixed graph at the top left in Figure 11.

MW?H??GC@_?EAO??E?_O?B@_??L_??W?@_ | MW?H??K??_QC??o?I??oCC??oGH@?ACH?? | MW?H??K??_QC??o?@c?_CC??oE?I??EH??
---|---|---
MW?H??K??_QC??o?B?A_CC??sC?AAACH?? | MW?H??K??_QC??o?BC?_CC??oCIA??K@_? | MW?H??G@@_?E?OA?E?_O?B?oG?OCG?KE??
MW?H??G@@_?E?OA?E?_O?B@_G?O?W?WE?? | MW?H??G@@_?E?OA?E?_O?B__?OO?W?WE?? | MW?H??G@@_?EAO??E?_O?B?__OO?W?WE??
MW?H??G@@_?EAO??E?_O?B?_c?O?W?WAO? | MW?H??G@@_?EAO??E?_O?B@_??W?W?WE?? | MW?H??G@@_?EAO??E?_O?B@_??X?G?WA@?
MW?H??G@@_?EAO??E?_O?BO_??W?W?WAO? | MW?H??G@@_?EAO??E?_O?BO_??WCG?WA@? | MW?H??GC@_?E?OA?E?_O?B?o?OD_?_G?@_
MW?H??GC@_?E?OA?E?_O?B@_?CD_?_G?@_ | MW?H??GC@_?E?OA?E?_O?B@_G?D_??W?@_ | MW?H??GC@_?E?OA?E?_O?B__?OD_??W?@_
MW?H??GC@_?E?P??E?_O?B__??L_??K?O_ | MW?H??GC@_?EAO??E?_O?B?o??Kc??KC?_ | MW?H??K??OQG?@_?E?OO?B__C?O?IAG@@?
MW?H??K??_Q@?@_?E?OO?BO_??WGG?WH?? | MW?H??K??_U??@_?E?OO?B?___O?W?WH?? | MW?H??K??_U??@_?E?OO?B?_g?O?W?W@_?
MW?H??K??‘A@?@_?E?OO?BO_??MO?AG?C_ | MW?H??GO@_?E?OO?B?_O?BW???MA?@G?C_ | MW?H??GC@_?E?OO?A__O?B_?OK?c?OG?@_
Table 2: All $27$ mixed graphs with largest order for $r=z=1$ and diameter
$k=4$ given as an ASCII string encoded in _digraph6_ representation (see McKay
and Piperno [22]). The first one in the list is precisely the Cayley graph
depicted in the top left of Figure 11. Figure 11: Some cospectral largest
mixed graphs with diameter $k=4$ and degrees $r{=}z{=}1$.

The spectra of all $27$ mixed graphs with the largest order can be described
with the help of the (complex) roots $\alpha_{ij}$ of the irreducible
polynomials $p_{i}(x)\in\mathbb{Q}(x)$ given below:

$\begin{array}[]{lll}p_{1}(x)=x^{4}+x^{3}-2x^{2}-x+2,\\\
p_{2}(x)=x^{3}+x^{2}-2x-1,\\\ p_{3}(x)=x^{3}-x+1,\\\
p_{4}(x)=x^{3}+2x^{2}-x-3,\\\ p_{5}(x)=x^{4}+x^{3}-x^{2}-x+1,\\\
p_{6}(x)=x^{6}+x^{5}-3x^{4}-x^{3}+5x^{2}-4,\\\
p_{7}(x)=x^{9}+3x^{8}-6x^{6}+2x^{5}+11x^{4}-3x^{3}-9x^{2}+3x+3,\\\
p_{8}(x)=x^{6}+x^{5}-3x^{4}-2x^{3}+5x^{2}+2x-3,\\\
p_{9}(x)=x^{6}+x^{5}-x^{4}+3x^{2}-1.\end{array}$

Number of graphs | Spectra
---|---
9 |  $\\{2^{1},0^{6},\alpha_{1j}^{1},\alpha_{2s}^{1}\\}$ for $j=1,2,3,4$ and $s=1,2,3$
6 |  $\\{2^{1},-1^{1},1^{1},0^{5},\alpha_{3j}^{1},\alpha_{4j}^{1}\\}$ for $j=1,2,3$
5 |  $\\{2^{1},0^{7},\alpha_{2j}^{2}\\}$ for $j=1,2,3$
4 |  $\\{2^{1},0^{3},\alpha_{5j}^{1},\alpha_{6k}^{1}\\}$ for $j=1,2,3,4$ and $k=1,\ldots,6$
2 |  $\\{2^{1},1^{1},0^{3},\alpha_{7j}^{1}\\}$ for $j=1,\ldots,9$
1 |  $\\{2^{1},0^{1},\alpha_{8j}^{1},\alpha_{9j}^{1}\\}$ for $j=1,\ldots,6$
Table 3: Classification of the largest mixed graphs for $r=z=1$ and diameter
$k=4$ according to their spectra. The third row gives the spectrum of the 5
cospectral graphs in Figure 11.

##  4 A second computational approach: Cayley or lift $(1,1,k)$-mixed graphs
with small diameter

To obtain the results of this section, we followed a different strategy. We
mainly concentrate our search on looking at large $(1,1,k)$-mixed graphs that
are either Cayley or lift graphs. Let us first recall these two classes of
graphs.

Given a finite group $\Omega$ with generating set $S\subseteq\Omega$, the
Cayley graph $\mbox{\rm Cay}(\Omega,S)$ has vertices representing the elements
of $\Omega$, and arcs from $\omega$ to $\omega s$ for every $\omega\in\Omega$
and $s\in S$. Notice that if $s,s^{-1}\in S$, then we have an edge (as two
opposite arcs) between $\omega$ and $\omega s$. Thus, if $S=S_{1}\cup S_{2}$
where $S_{1}=S_{1}^{-1}$ and $S_{2}\cap S_{2}^{-1}=\emptyset$, the Cayley
graph $\mbox{\rm Cay}(\Omega,S)$ is an $(r,z)$-mixed graph with undirected
degree $r=|S_{1}|$ and directed degree $z=|S_{2}|$.

Given a digraph $G$, or base graph, and a finite group $\Omega$ with
generating set $S$, a voltage assignment $\alpha$ is a mapping
$\alpha:E\rightarrow S$, that is, a labeling of the arcs with the elements of
$S$. Then, the lift digraph $G^{\alpha}$ has vertex set
$V(G^{\alpha})=V\times\Omega$ and arc set $E(G^{\alpha})=E\times S$, where
there is an arc from vertex $(u,g)$ to vertex $(v,g\alpha(uv))$ if and only if
$uv\in E$. In particular, the Cayley digraph $\textrm{Cay}(\Omega,S)$ with
$S=\\{g_{1},\ldots,g_{r}\\}$ can be seen as the lifted digraph $G^{\alpha}$,
where $G=K_{1}^{r}$ (a singleton with $V=\\{u\\}$ and
$E=\\{e_{1},\ldots,e_{r}\\}$ are $r$ loops) and voltage assignment
$\alpha(e_{i})=g_{i}$ for $i=1,\ldots,r$. An example of a lift digraph is
shown in Figure 12.

Figure 12: A base graph with voltages on the symmetric group $S_{3}$, and its
lift graph.

The results obtained by computer search are shown in Table 4, see next
section. In what follows, we comment upon some of the cases. Notice that for
diameter $k=2,3,4$, the known $(1,1,k)$-mixed graphs have the maximum possible
order. The mixed graph of diameter $k=2$ is the Kautz digraph $K(2,2)$. The
graph with $k=3$ is isomorphic to the line digraph of the cycle $C_{5}$. Some
of the maximal graphs with diameter $k=4$ were already shown in Figure 11.

Two maximal graphs of diameter $k=5$ are shown in Figure 13.

Figure 13: Two $(1,1,5)$-mixed graphs with defect 8 and order 24.

The graph of order $72$ listed in the table for $k=8$ is a lift graph using
the dihedral group $D_{18}$ of order $18$. This group consists of the $18$
symmetries of the nonagon. To describe our graph, we consider a regular
nonagon whose vertices are labeled $0$ to $8$ in clockwise order. Label the
elements of $D_{18}$ as follows. There are nine counter-clockwise rotations,
each through an angle $2\pi k/9$ and denoted Rot(k), for $0\leq k<9$. Finally,
there are the nine reflections Ref(k) about the line through vertex $k$ and
the midpoint of the opposite side. This notation is used to specify the
voltages on the edges and arcs of the base graph shown in Figure 14.

Figure 14: The base graph of the $(1,1,8)$-mixed graph of order $72$.

The graph of order $544$ for $k=13$ is a lift of the base graph shown in
Figure 15 with voltages in the group $\mathbb{Z}_{17}:\mathbb{Z}_{8}$.

Figure 15: The base graph of the $(1,1,13)$-mixed graph of order $544$.

The remaining graphs are partially identified as notes following Table 4.
Where a graph is identified as a lift using a voltage group of order half the
order of the graph, the base graph is an undirected edge together with a
directed loop at each vertex. A complete description of such larger graphs,
especially those that use unfamiliar groups, would take a lot of pages. The
interested reader can address the third author to request more information.

##  5 Table of large $(1,1,k)$-mixed graphs

A summary of the results for a $(1,1)$-regular mixed graphs with diameter $k$
at most $16$ is shown in Table 4, where the lower bounds come from the
mentioned constructions. Moreover, the upper bounds follow by Proposition 3.2
$(k=4)$, a computer exploration $(k=5)$, and the numbers $M(1,1,k)-\delta(k)$
with $\delta(k)$ given in (3) and adjusted even parity (since $r=1$, the graph
contains a perfect matching and, so, it must have even order), see Tuite and
Erskine [27].

$k$ | Lower bound | Upper bound | Moore $M(1,1,k)$ | Notes
---|---|---|---|---
2 | 6 | 6 | 6 |
3 | 10 | 10 | 11 |
4 | 14 | 14 | 19 |
5 | 24 | 26 | 32 |
6 | 34 | 48 | 53 |
7 | 54 | 78 | 87 | Cayley111Cayley graph on SmallGroup(54,6): $Z_{9}:Z_{6}$.
8 | 72 | 126 | 142 | Lift222Lift group is the dihedral group of order 18.
9 | 112 | 206 | 231 | Lift333Lift group is $AGL(1,8)$.
10 | 144 | 336 | 375 | Cayley444Cayley graph on SmallGroup(144,182).
11 | 240 | 544 | 608 | Lift555Lift group $A_{5}\times Z_{2}$
12 | 336 | 882 | 985 | Lift666Cayley graph on $PSL(2,7):Z_{2}$.
13 | 544 | 1428 | 1595 | Lift777Lift group $Z_{17}:Z_{8}$
14 | 800 | 2312 | 2582 | Cayley888group SmallGroup(800,1191).
15 | 1024 | 3744 | 4179 | Lift999Lift group SmallGroup(512,1727)
16 | 1600 | 6058 | 6763 | Lift101010Lift group SmallGroup(800,1191)
Table 4: Bounds for mixed graphs with $(r,z,k)=(1,1,k)$.

  1. 1.

Cayley graph on SmallGroup(54,6): $\mathbb{Z}_{9}:\mathbb{Z}_{6}$.

  2. 2.

Lift group is the dihedral group of order 18.

  3. 3.

Lift group is
$AGL(1,8)=(\mbox{\boldmath$Z$}_{2}^{3}):\mbox{\boldmath$Z$}_{7}$.

  4. 4.

Cayley graph on SmallGroup(144,182).

  5. 5.

Lift group is $A_{5}\times\mathbb{Z}_{2}$.

  6. 6.

Cayley graph on $PSL(2,7):\mathbb{Z}_{2}$.

  7. 7.

Lift group is $\mathbb{Z}_{17}:\mathbb{Z}_{8}$.

  8. 8.

Cayley graph on SmallGroup(800,1191).

  9. 9.

Lift group is SmallGroup(512,1727).

  10. 10.

Lift group is SmallGroup(800,1191).

##  6 Statements & Declarations

###  6.1 Funding

The research of C. Dalfó, M. A. Fiol, N. López, and A. Messegué has been
supported by AGAUR from the Catalan Government under project 2021SGR00434 and
MICINN from the Spanish Government under project PID2020-115442RB-I00. The
research of M. A. Fiol was also supported by a grant from the Universitat
Politècnica de Catalunya with references AGRUPS-2022 and AGRUPS-2023. J. Tuite
was supported by EPSRC grant EP/W522338/1.

###  6.2 Competing Interests

The authors have no relevant financial or non-financial interests to disclose.

###  6.3 Author Contributions

All authors contributed to the study’s conception and design. Material
preparation, data collection, and analysis were performed by all the authors,
after much work was done. All authors contributed to the first draft of the
manuscript, which was improved by all of them. All authors read and approved
the final manuscript.

###  6.4 Data availability

The datasets generated during and/or analyzed during the current study are
available from the corresponding author upon reasonable request.

## References

  * [1] E. Baskoro, M. Miller, and J. Plesník, On the structure of digraphs with order close to the Moore bound, Graphs Combin. 14  (1998), no. 2, 109–119.
  * [2] J. Bosák, Partially directed Moore graphs, Math. Slovaca 29 (1979) 181–196.
  * [3] D. Buset, M. El Amiri, G. Erskine, M. Miller, and H. Pérez-Rosés, A revised Moore bound for mixed graphs, Discrete Math. 339 (2016), no. 8, 2066–2069.
  * [4] D. Buset, N. López, and J. M. Miret, The unique mixed almost Moore graph with parameters $k=2$, $r=2$ and $z=1$, J. Intercon. Networks 17 (2017) 1741005\.
  * [5] C. Dalfó, A new general family of mixed graphs, _Discrete Appl. Math_ 269 (2019) 99–106.
  * [6] C. Dalfó and M. A. Fiol, Cospectral digraphs from locally line digraphs, _Linear Algebra Appl._ 500 (2016) 52–62.
  * [7] C. Dalfó, M. A. Fiol, and N. López, Sequence mixed graphs, Discrete Applied Math. 219 (2017) 110–116.
  * [8] C. Dalfó, M. A. Fiol, and N. López, An improved upper bound for the order of mixed graphs, Discrete Math. 341 (2018), no. 10, 2872–2877.
  * [9] C. Dalfó, M. A. Fiol, and N. López, On bipartite-mixed graphs, J. Graph Theory 89 (2018) 386–394.
  * [10] T. Dobravec and B. Robič, Restricted shortest paths in $2$-circulant graphs, Comput. Commun. 32 (2009), no. 4, 685–690.
  * [11] H. Dweighter, Elementary problems and solutions, problem E2569, _Amer. Math. Monthly_ 82 (1975), no. 10, 1010.
  * [12] P. Erdős, S. Fajtlowicz, and A. J. Hoffman, Maximum degree in graphs of diameter $2$, Networks 10 (1980) 87–90.
  * [13] G. Erskine, Mixed Moore Cayley graphs, J. Intercon. Networks 17, no. 03n04, (2017) 1741010.
  * [14] V. Faber, J. W. Moore, and W. Y. C. Chen, Cycle prefix digraphs for symmetric interconnection networks, _Networks_ 23 (1993) 641–649.
  * [15] M. A. Fiol, J. L. A. Yebra, and I. Alegre, Line digraph iterations and the $(d,k)$ digraph problem, IEEE Trans. Comput. C-33 (1984) 400–403.
  * [16] J. Gimbert, Enumeration of almost Moore digraphs of diameter two, Discrete Math. 231 (2001) 177–190.
  * [17] A. J. Hoffman and M. H. McAndrew, The polynomial of a directed graph, Proc. Amer. Math. Soc. 16 (1965) 303–309.
  * [18] L. K. Jørgensen, New mixed Moore graphs and directed strongly regular graphs, Discrete Math. 338 (6) (2015) 1011–1016.
  * [19] N. López and J. M. Miret, On mixed almost Moore graphs of diameter two, Electron. J. Combin. 23(2) (2016) 1–14.
  * [20] N. López, J. M. Miret, and C. Fernández, Non existence of some mixed Moore graphs of diameter 2 using SAT, Discrete Math. 339(2) (2016) 589–596.
  * [21] N. López, H. Pérez-Rosés, and J. Pujolàs, Mixed Moore Cayley graphs, Electron. Notes Discrete Math. 46 (2014) 193–200.
  * [22] B. D. McKay and A. Piperno, Nauty and Traces User’s Guide (Version 2.27). Technical Report, Computer Science Department, Australian National University (2021).
  * [23] M. Miller and J. Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, Electron. J. Combin. 20(2) (2013) #DS14v2.
  * [24] M. H. Nguyen, M. Miller, and J. Gimbert, On mixed Moore graphs, Discrete Math. 307 (2007) 964–970.
  * [25] OEIS Foundation Inc. (2022), The On-Line Encyclopedia of Integer Sequences, Published electronically at http://oeis.org.
  * [26] J. Tuite and G. Erskine, On total regularity of mixed graphs with order close to the Moore bound, Graphs Combin. 35 (2019), no. 6, 1253–1272.
  * [27] J. Tuite, and G. Erskine, On networks with order close to the Moore bound, Graphs Combin. 38 (2022), no. 5, 143.