Cristina Dalfo´ a , Miquel Angel Fiol ` ^b

^aDepartament de Matematica, Universitat de Lleida, Igualada (Barcelona), Catalonia ` <sup>b</sup>Departament de Matematiques, Universitat Polit ` ecnica de Catalunya, Barcelona Graduate School, ` Institut de Matematiques UPC-BarcelonaTech (IMTech), Barcelona, Catalonia `

cristina.dalfo@udl.cat, miguel.angel.fiol@upc.edu

A Moore (r, z, k)-mixed graph G has every vertex with undirected degree r, directed in- and outdegree z, diameter k, and number of vertices (or order) attaining the corresponding Moore bound M(r, z, k) for mixed graphs. When the order of G is close to M(r, z, k) vertices, we refer to it as an almost Moore graph. The first part of this paper is a survey about known Moore (and almost Moore) general mixed graphs that turn out to be Cayley graphs. Then, in the second part of the paper, we give new results on the bipartite case. First, we show that Moore bipartite mixed graphs with diameter three are distance-regular, and their spectra are fully characterized. In particular, an infinity family of Moore bipartite (1, z, 3)-mixed graphs is presented, which are Cayley graphs of semidirect products of groups. Our study is based on the line digraph technique, and on some results about when the line digraph of a Cayley digraph is again a Cayley digraph.

Keywords: mixed graph, Moore bound, Cayley graph, line digraph, spectrum Mathematics Subject Classification: 05C50, 05C20, 15A18, 20C30

DOI: 10.5614/ejgta.2023.11.1.15

1. Preliminaries

Mixed graphs can be suitable models for networks having both bidirectional and unidirectional links. Thus, a mixed graph G = (V, E, A) has a set V = V (G) of vertices, a set E = E(G) of edges, and a set A = A(G) of arcs or directed edges. For a given vertex u ∈ V , its undirected degree r(u) is the number of edges incident to vertex u. Moreover, its out-degree z ⁺(u) is the

Received: 31 July 2022, Revised: 27 February 2023, Accepted: 25 March 2023.

Figure 1. The Bosak´ (3, 1)-graph with diameter k = 2 and N = 18 vertices.

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 ∈ V , then G is said to be an (r, z)-regular mixed graph or, simply, an (r, z)-mixed graph, with whole degree d = r + z.

The distance from vertex u to vertex v is denoted by dist(u, v). Notice that, when z 6= 0, dist(u, v) is not necessarily equal to dist(v, u). If the mixed graph G has diameter k, its distance matrix Aⁱ , for i = 0, 1, . . . , k, has entries (Ai)uv = 1 if dist(u, v) = i, and (Ai)uv = 0 otherwise. So, A⁰ = I (the identity matrix) and A¹ = A (the adjacency matrix of G).

Mixed graphs were first considered in the context of the degree/diameter problem by Bosak [1]. ´ Similarly, in the case of regular graphs or digraphs, the (r, z, k) problem for mixed graphs consists of finding the largest possible number of vertices N(r, z, k) in a mixed graph with maximum undirected degree r, maximum directed out-degree z, and diameter k. For more results on this problem on graphs (and mixed graphs), see the comprehensive survey by Miller and Sir ˇ a´n [18]. ˇ For more results on mixed graphs, see Buset, Lopez, and Miret [4], Dalf ´ o [5], Dalf ´ o, Fiol, and ´ Lopez [6], Erskine [9], Jørgensen [14], L ´ opez, P ´ erez-Ros ´ es, and Pujol ´ as [17], Nguyen, Miller, and ` Gimbert [19], and Tuite and Erskine [20].

An example of a (3, 1)-regular mixed graph is shown in Figure 1. It was proposed by Bosak´ [1], as an example of a mixed graph with maximum number of vertices (that is, attaining the corresponding Moore bound) for r = 3, z = 1, and diameter k = 2.

Given a finite group Ω with generating set S ⊆ Ω, the Cayley graph Cay(Ω, S) has vertices representing the elements of Ω, and arcs from ω to ωs for every ω ∈ Ω and s ∈ S. Notice that, if s, s⁻¹ ∈ S, then we have an edge (a digon or two opposite arcs) between ω and ωs. Thus, if S = S¹ ∪ S² where S¹ = S −1 1 and S² ∩ S −1 ² = ∅, the Cayley graph Cay(Ω, S) is an (r, z)-mixed graph with undirected degree r = |S1| and directed degree z = |S2|.

The existence of Moore (r, z, 2)-mixed graphs, usually called simply 'Moore digraphs', which are Cayley, have been studied by some authors. Apart from the case r = 1, only three Moore digraphs are known, which are also Cayley graphs. Namely, the already mentioned Bosak digraph, ´ and the two digraphs of Jørgensen [14]; see later Theorem 3.2 by Erskine [9]. Some proofs of the non-existence of Cayley Moore digraphs for some order values have been given by Lopez, P ´ erez- ´ Roses, and Pujol ´ as [17], L ` opez, Miret, and Fern ´ andez [16] , Erskine [9], and Gavrilyuk, Hirasaka, ´

and Kabanov [12].

In our study, we also use the line digraph technique. Recall that, given a digraph G, its line digraph LG has vertices representing the arcs of G, and vertex uv of LG (corresponding to the arc u → v in G) is adjacent to the vertices vw for any w adjacent from v in G. See Fiol, Yebra, and Alegre [11].

The first part of this paper is a brief survey about known Moore (and almost Moore) general mixed graphs that turn out to be Cayley graphs. More information about Cayley Moore mixed graphs can be found in the paper by Erskine [9]. Our main contribution is described in the second part of the paper, where we give new results on the bipartite case. This can be a follow-up of the previous research on the degree/diameter problem for bipartite mixed graphs done by the authors and Lopez [7, 8]. In this context, we here show that Moore bipartite mixed graphs with diameter ´ three are distance-regular, and their spectra are fully characterized. In particular, an infinity family of Moore bipartite (1, z, 3)-mixed graphs is presented, which are Cayley graphs of semidirect products of groups.

2. Moore mixed graphs

The following result gives the maximum possible number of vertices, or Moore bound, of an (r, z)-mixed graph with diameter k.

Theorem 2.1 (Buset, El Amiri, Erskine, Miller, and Perez-Ros ´ es [3]) ´ . The Moore bound for an (r, z)-regular 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

\[u_1 = \frac{z + r - 1 - \sqrt{v}}{2}, \qquad u_2 = \frac{z + r - 1 + \sqrt{v}}{2},\] \[A = \frac{\sqrt{v} - (z + r + 1)}{2\sqrt{v}}, \qquad B = \frac{\sqrt{v} + (z + r + 1)}{2\sqrt{v}},\] \[v = (z + r)^2 + 2(z - r) + 1.\]

The largest value of M(r, z, k) for fixed k and given whole degree d is obtained when r = 0 and z = d (a d-regular digraph), which is

\[M(0,d,k) = \frac{d^{k+1} - 1}{d-1}.\]

Nguyen, Miller, and Gimbert [19] proved that the Moore bound M(r, z, k) cannot be attained for diameter k ≥ 3. In the case of diameter 2, we have the following result, which was proved by using matrix and eigenvalue techniques.

Figure 2. The unique three non-isomorphic (1, 1)-regular mixed graphs with diameter k = 3 and order N = 10.

Theorem 2.2 (Bosak, 1979) ´ . Let G be an (r, z)-mixed graph with diameter k = 2. Apart from the trivial cases (z, r) = (1, 0),(0, 2), there must be a positive odd integer c such that

\[c \mid (4z-3)(4z+5)\] and \(r = \frac{1}{4}(c^2+3)\).

In fact, the upper bound of Theorem 2.1 can be slightly improved, as shown in the next theorem.

Theorem 2.3 (Dalfo, Fiol, and L ´ opez [8]) ´ . The order N of an (r, z)-regular mixed graph G with diameter k ≥ 3 satisfies

\[N \le M(r, z, k) - r,\]

where M(r, z, k) is the Moore bound given in (1).

For the case of diameter two, we get

\[N \le M(r, z, 2) = (r + z)^2 + z + 1.\]

Moreover, by using a simple parity argument (namely, when r is odd, N must be even), we obtain the following result.

Proposition 2.1 (Dalfo, Fiol, and L ´ opez [8]) ´ . Let G be an (r, z)-regular mixed graph of diameter k ≥ 3 with order N. If r and z are odd and k ≡ 2 (mod 3), then

\[N \le M(r, z, k) - r - 1.\]

For the case r = z = 1, Tuite and Erskine [21] gave an improved bound for Theorem 2.3. For optimal (1, 1)-regular mixed graphs with diameter 3, we have the following result.

Proposition 2.2 (Dalfo, Fiol, and L ´ opez [8]) ´ . Let G be a (1, 1)-regular mixed graph with diameter k = 3 and maximum order N = 10 = M(1, 1, 3) − 1. Then G is isomorphic to one of the three mixed graphs in Figure 2, satisfying the following properties:

• The mixed graph (a) is the line digraph of the cycle C⁵ (seen as a digraph, with five digons), and it is isomorphic to the Cayley digraph of the dihedral group D⁵ = hr, s | r ⁵ = s ² = (rs) ² =1i. That is,

\[LC_5 \cong \operatorname{Cay}(D_5, \{r, s\}).\]

Figure 3. The (1,1)-regular mixed graph with diameter k=3 and order N=10 as the line digraph of the directed cycle \(C_5\).

• The mixed graphs (a), (b), and (c) are isomorphic to their converse digraphs (obtained by reversing the direction of the arcs) and cospectral, with spectrum

\[\left\{2, \left(-\frac{1}{2} + \frac{\sqrt{5}}{2}\right)^{[2]}, 0^{[5]}, \left(-\frac{1}{2} - \frac{\sqrt{5}}{2}\right)^{[2]}\right\} = \operatorname{sp}(C_5) \cup \{0^{[5]}\}.\]

3. Moore Cayley mixed graphs

It is natural to ask what d-regular Cayley digraphs G have the property that their line digraph LG is also Cayley. Let \(K_d^+(S)\) be the complete symmetric digraph with loops, and vertex set S with cardinality d. A decomposition into permutations of \(K_d^+(S)\) is a set \(\Pi\) of permutations of S such that, for every arc (s,t), there is a unique \(\pi \in \Pi\) such that \(t=\pi(s)\). Note that this corresponds to an arc-coloring of \(K_d^+(S)\), where \(\pi\) is the 'color' of (s,t). A decomposition into permutations \(\Pi = \{\pi_s : s \in S\}\) is normal if, for some \(s_1 \in S\), the following conditions hold:

• (i) \(\pi_{s_1} = e\) (the identity).
• (ii) \(\pi_s(s_1) = s\) for all \(s \in S\).

That is, in terms of arc-coloring, all loops get the same color \(\pi_{s_1}\), and the arc \((s_1, s)\) is colored by \(\pi\).

It is convenient to take normal decompositions for uniformly induced colorings.

Theorem 3.1 (Fiol, Fiol, and Yebra [10]). Let \(G = \operatorname{Cay}(\Omega, S)\) be a Cayley digraph, and \(\Pi = \{\pi_s : s \in S\}\) a normal decomposition into permutations of \(K_d^+(S)\) with \(\pi_{s_1} = e\). Then the line digraph LG is a Cayley digraph if and only if \(\Pi\) is a group of automorphisms of \(\Omega\). In this case, LG is isomorphic to a Cayley digraph on the semidirect product \(\Omega \rtimes \Pi\), with generating set \(S = \{(s_1, \pi_s) : s \in S\}\).

The Kautz digraph K(d,2), with degree d and diameter k=2, can be defined as the line digraph of the complete graph on d+1 vertices with every edge being a digon (two opposite arcs), that is,

\[K(d,2) = LK_{d+1}.\]

Figure 4. Left: The Kautz digraph K(2,2) as the Cayley graph of the semidirect product \((\mathbb{F}_3,+) \rtimes \mathbb{F}_3^*\). Right: The Kautz digraph K(2,2) as the Cayley graph of the dihedral group \(D_3 = \langle a,b \,|\, a^3 = b^2 = (ab)^2 = e \rangle\).

Proposition 3.1 (Brunat, Espona, Fiol, and Serra [2]). The Kautz digraph K(d, 2) is a Cayley graph if and only if d + 1 is a prime power.

Proof. For completeness, we prove sufficiency. If \(d+1=p^m\), with p a prime, let \(\Omega\) be the additive group of the finite field \(\mathbb{F}_{d+1}\). For every \(s\in S=\mathbb{F}_{d+1}^*=\mathbb{F}_{d+1}\setminus\{0\}\), let \(\pi_s\) be the automorphism of \(\mathbb{F}_{d+1}\) defined by \(\pi_s(x)=sx\). Then, \(\Pi=\{\pi_s:s\in S\}\) is a normal decomposition into permutations of \(K_d^+(S)\) with \(s_1=1\), and it is a group of automorphisms of \(\mathbb{F}_{d+1}\). Thus, by Theorem 3.1, \(K(d,2)=LK_{d+1}\cong \operatorname{Cay}(\Omega,\mathcal{S})\) is a Cayley digraph with \(\Omega=(\mathbb{F}_{d+1},+)\rtimes\mathbb{F}_{d+1}^*\) and \(\mathcal{S}=\{(1,s):s\in S\}\).

Therefore, the vertices of K(d,2) correspond to the pairs \((g,\mu)\), with \(g \in (\mathbb{F}_{d+1},+)\) and \(\mu \in S = \mathbb{F}_{d+1}^*\), and the arcs correspond to the pairs (1,s), for \(s \in S\). Then, the vertex \((g,\mu)\), through the arc labeled (1,s), is adjacent to the vertex:

\[(g,\mu)(1,s) = (g + \pi_{\mu}(1), \pi_{\mu} \circ \pi_s) = (g + \mu, \mu s).\]

In Figure 4, we show the case r=z=1, with the Kautz digraph K(2,2) as the Cayley graph of the semidirect product \((\mathbb{F}_3,+) \rtimes \mathbb{F}_3^*\). For instance, from vertex (1,2) through the arc (1,1), we get the vertex \((1,2)(1,1)=(1+2,2\cdot 1)=(0,2)\).

For the case r = 3 and z = 1, the following result is known.

Proposition 3.2 (López, Pérez-Rosés, and Pujolàs [17]). The Bosák graph is a mixed Cayley graph that can be obtained from either \(S_3 \times \mathbb{Z}_3\) or \((\mathbb{Z}_3 \times \mathbb{Z}_3) \rtimes \mathbb{Z}_2\).

Besides, for the case (r, z, 2), Erskine [9] gave the next theorem.

Theorem 3.2 (Erskine [9]). The only Moore Cayley (r, z, 2)-mixed graphs with order \(N \le 485\) are the following:

• r = 1 and \(z \le 20\), where z + 2 is a prime power (Kautz graphs).
• r = 3 and z = 1 (Bosák's graph [1]).
• r = 3 and z = 7 (the two Jørgensen's graphs [14]).

Recall that Bosák's graph is shown in Figure 1.

4. The bipartite case

For the bipartite mixed graphs, the following result gives a new upper bound.

Theorem 4.1 (Dalfo, Fiol, and L ´ opez [7]) ´ . With A, B, u1, u² defined as in (1), the Moore bound for an (r, z)-regular bipartite mixed graph is

\[M_B(r, z, k) = 2\left(A\frac{u_1^{k+1} - u_1}{u_1^2 - 1} + B\frac{u_2^{k+1} - u_2}{u_2^2 - 1}\right), \quad r > 0.\]

The following result was also proved in [7].

Proposition 4.1 (Dalfo, Fiol, and L ´ opez [7]) ´ . Bipartite mixed Moore graphs do not exist for any r ≥ 1, z ≥ 1, and k = 2 or k ≥ 4.

4.1. The case of diameter 3

Now we concentrate on the case of diameter three. Let G be a Moore bipartite (r, z, 3)-mixed graph with adjacency matrix

\[\boldsymbol{A} = \left(\begin{array}{cc} \boldsymbol{0} & \boldsymbol{A}_1 \ \boldsymbol{A}_2 & \boldsymbol{0} \end{array}\right).\]

In this case, we get

\[M_B(r, z, 3) = 2[(r+z)^2 - r + 1].\] (2)

In particular, MB(1, z, 3) = 2(1 + z) 2 and MB(r, 1, 3) = 2r ² + 3(r + 1).

By analogy with the case of graphs, we say that a digraph or mixed graph G, with diameter k and adjacency matrix A, is distance-regular if there exist polynomials p0(x), p1(x), . . . , pk(x), with deg pⁱ = i, that applied to A give the corresponding distance matrices Aⁱ = pi(A) for i = 0, 1, . . . , k. In the following result, we show that this is the case for Moore bipartite mixed graphs of diameter three.

Lemma 4.1. The Moore bipartite mixed graph with diameter 3 is distance-regular.

Proof. Let G be a Moore bipartite (r, z, 3)-mixed graph with adjacency matrix A. Let us prove that its distance polynomials are the following.

\[p_0(x) = 1,\] \[p_1(x) = x,\] \[p_2(x) = x^2 - r,\] \[p_3(x) = \frac{x^3 - (r - 1)x}{r + z} - x.\]

The first two polynomials are trivial because of A⁰ = I and A¹ = A. In the expression of p2(x), we must consider that there are r paths from every vertex to itself. (Indeed, they arise by following an undirected edge in both directions.) Concerning p3(x), notice that, since the diameter is k = 3, there should exist just one path of length 0 or 2 from any vertex u to any other vertex v of its partite set. Such paths correspond to the 1's of the matrix A⁰ + A² = p0(A) + p2(A). Therefore, there are exactly r + z paths of length 1 or 3 from u to any vertex w of the other partite set. Hence, A¹ + A³ = 1 r+z (A⁰ + A2)A and, A³ = p3(A) with the claimed polynomial p3(x).

Figure 5. A Moore bipartite (2, 1, 3)-mixed graph.

From this last lemma, we can derive the spectra of Moore bipartite mixed graphs of diameter 3.

Proposition 4.2. The spectrum of a Moore bipartite (r, z, 3)-mixed graph G with order n given by (2) is

\[\operatorname{sp} G = \left\{ \pm (r+z), \pm \sqrt{r-1}^{\left[\frac{n-2}{2}\right]} \right\}.\]

Proof. The eigenvalue r + z is due to the regularity of G. Moreover, the sum of the distance polynomials equals the Hoffman polynomial H that applied to A gives the all-1 matrix J (see Hoffman and McAndrew [13]):

\[H(\mathbf{A}) = \sum_{i=0}^{3} p_i(\mathbf{A}) = \frac{1}{r+z}\mathbf{A}^3 + \mathbf{A}^2 + \frac{1-r}{r+z}\mathbf{A} - (r-1)\mathbf{I} = \mathbf{J}.\]

Note that \({\bm J}\) has eigenvalues n with multiplicity 1 and 0 with multiplicity n-1. Then, the other eigenvalues of G are the roots of the polynomial \(H(x)=\frac{1}{r+z}x^3+x^2+\frac{1-r}{r+z}x+1-r\), namely, \(-(r+z),\pm\sqrt{r-1}\). In fact, the eigenvalue r+z can also be obtained as the solution of H(x)=n. Since G is bipartite, its spectrum is symmetric around 0. So, since the multiplicity of \(\pm(r+z)\) is 1, the one of \(\pm\sqrt{r-1}\) is equal to \(\frac{n-2}{2}\).

For instance, for the Moore bipartite mixed graph of Figure 5 with r=2, z=1, diameter 3, and 16 vertices, the distance polynomials are \(p_0=1, p_1=x, p_2=x^2-2\), and \(p_3=\frac{1}{3}(x^3-4x)\), and its spectrum is \(\{\pm 3, \pm 1^{[7]}\}\). This mixed graph can be constructed as the Cayley graph

Figure 6. The two bipartite (1, 1, 3)-mixed graphs attaining the Moore bound.

\(Cay(\Omega, \{\alpha, \beta, \gamma\})\), where \(\Omega\) is the direct product of the dihedral group with 8 elements with the cyclic group of 2 elements, with standard presentation

\[D_8 \times \mathbb{Z}_2 = \langle a, b, c | a^4 = b^2 = c^2 = e, bab^{-1} = a^{-1}, ac = ca, bc = cb \rangle,\]

and generators \(\alpha = a\), \(\beta = b\), and \(\gamma = abc\) (in Figure 5, they give rise to arcs, solid edges, and dotted edges, respectively).

Observe that, according to Proposition 4.2, the Moore bipartite mixed graphs of diameter 3 could exist for any value of r and z. Instead, in the case of general Moore mixed graphs of diameter 2, some conditions must be satisfied for their existence (see Theorem 1).

The distance polynomials are orthogonal with respect to the scalar product

\[\langle f, g \rangle_G = \frac{1}{n} \operatorname{tr}[f(\boldsymbol{A})g(\boldsymbol{A})^{\top}],\]

so that \(||p_i||_G^2 = p_i(r+z) = |G_i(u)|\) gives the number of vertices at distance \(i \in [0, k]\) from any vertex u of G.

Next, we present an infinite family of Moore bipartite mixed graphs with diameter 3, and we show that they are Cayley graphs of a semidirect product of groups. More precisely, we prove that bipartite mixed Moore graphs with diameter k=3 and r=1, on \(2(1+z)^2\) vertices, exist for any value of \(z\geq 1\). In particular, when z=1, there exist two non-isomorphic Moore bipartite (1,1,3)-mixed graphs.

Lemma 4.2. Let G be a (1,1)-regular bipartite mixed graph with diameter k=3 and maximum order \(N=8=M_B(1,1,3)\). Then G is isomorphic to one of the two bipartite mixed graphs shown in Figure 6.

In fact, the first mixed graph of Figure 6 is a particular example of the infinite family described in the following result.

Theorem 4.2. Let \(D_n = \langle a, b | a^n = b^2 = (ab)^2 = e \rangle\) be the dihedral group with 2n elements, and let \(C_n\) be the cycle group with elements in \(\mathbb{Z}_n\). Then, the Moore bipartite (1, z, 3)-mixed graph

Figure 7. The complete bipartite graph \(K_{3,3}\) as the Cayley graph of the dihedral group \(D_3 = \langle a, b \mid a^3 = b^2 = (ab)^2 = e \rangle\) with generating set having involutive elements \(s_0 = b\), \(s_1 = ab\), and \(s_2 = a^2b\).

G, with z = n - 1 and \(2n^2\) vertices, is isomorphic to the Cayley graph on the semidirect product \(D_n \rtimes C_n\), with generating elements (b,i) for \(i = 0,1,\ldots,n-1\):

\[G = LK_{n,n} \cong Cay(D_n \rtimes C_n, \{(b,0), (b,1), \dots, (b,n-1)\}).\]

Proof. The proof proceeds as follows. First, notice that the complete bipartite graph \(K_{n,n}\) is isomorphic to the Cayley graph of the dihedral group \(D_n = \langle a, b \, | \, a^n = b^2 = (ab)^2 = e \rangle\) with generating set

\[S = \{ s_i = a^i b : i = 0, 1, \dots, n - 1 \}.\]

With this presentation, the independent sets of \(K_{n,n}\) are \(V_1 = \{a^i : i = 0, 1, ..., n-1\}\) and \(V_2 = V_1 b = S\). Moreover, since \(aba = b^{-1} = b\), we have

\[s_i^2 = a^i b a^i b = a^{i-1} b a^{i-1} b = \dots = abab = bb = e,\]

so that all generators in S are involutive. The set of permutations \(\pi_h \equiv \pi_{s_h}\), for \(h = 0, \dots, n-1\), of the elements of S, defined as

\[\pi_h(s_i) = s_{i+h}, \quad s_i \in S,\]

with addition understood modulo n, satisfies \(\pi_0 = e\) (the identity) and \(\pi_h(s_0) = s_h\). Thus, \(\Pi = \{\pi_0, \dots, \pi_{n-1}\}\) is a normal decomposition into permutations of \(K_n^+(S)\). To show that \(\Pi\) is a group of automorphisms of \(D_n\), let us see first that it can be extended to the elements of \(V_1\). With this aim, we define \(\pi_h(s_is_0) := \pi(s_h)\pi(s_0)\). Then, from \(a^i = a^ibb = s_ib = s_is_0\), for \(i = 0, \dots, n-1\), we have

\[\pi_h(a^i) = \pi_h(s_i s_0) = \pi_h(s_i)\pi_h(s_0) = s_{i+h}s_h = a^{i+h}ba^hb = a^ibb = a^i.\]

From this, it is readily seen that the elements of \(\Pi\) are automorphisms of \(D_n\). For instance,

\[\pi_h(a^i s_j) = \pi_h(a^{i+j}b) = \pi_h(s_{i+j}) = s_{i+j+h} = a^i a^{j+h}b\]\[= a^i s_{j+h} = \pi_h(a^i) \pi_h(s_j),\]

Figure 8. LK3,³ = Cay(D³ o C3, {(b, 0),(b, 1),(b, 2)}).

and, assuming that i ≥ j (and using again that a j ba^j = b),

\[\pi_h(s_i s_j) = \pi_h(a^i b a^j b) = \pi_h(a^{i-j} b b) = \pi_h(s_{i-j} s_0)\] \[= \pi_h(s_{i-j}) \pi_h(s_0) = s_{i-j+h} s_h = a^{i-j+h} b a^h b = a^{i+h} b a^{j+h} b\] \[= s_{i+h} s_{j+h} = \pi_h(s_i) \pi_h(s_j).\]

Consequently, Π is a group automorphism of Dn, isomorphic to the cycle group, Π ∼= Cn, fixing each element of V1, and the result follows from Theorem 3.1.

By way of example, for r = 1 and z = 2, the Cayley graphs isomorphic to K3,³ and to the line digraph LK3,³ are shown in Figure 7 and Figure 8, respectively. Note that in the last figure, each vertex is labeled in two ways: as a vertex of the line digraph LK3,3, and as a vertex of a Cayley graph on the group D³ o C3. We see, for instance, that as a line digraph, the vertex 54 is adjacent, through the dotted arc, to vertex 43. Accordingly, as a Cayley graph, vertex (a 2 , 1) is adjacent, through the generator (b, 1), to

\[(a^2, 1) \cdot (b, 1) = (a^2 \pi_1(b), 2) = (a^2 \pi_1(s_0), 2) = (a^2 s_1, 2) = (a^2 ab, 2) = (b, 2).\]

By Proposition 4.2, these Moore bipartite (1, z, 3)-mixed graphs have distance polynomials p⁰ = 1, p¹ = x, p² = x ² − 1, and p³ = 1 ^z+1x ³ − x, and spectrum {±(1 + z), ±0 [n−2]}.

Acknowledgment

We thank the anonymous referee that contributed to improve this paper with valuable comments.

This research has been partially supported by AGAUR from the Catalan Government under project 2021SGR00434 and MICINN from the Spanish Government under project PID2020-115442RB-I00.

References

• [1] J. Bosak, Partially directed Moore graphs, ´ Math. Slovaca 29 (1979), no. 2, 181–196.
• [2] J. M. Brunat, M. Espona, M. A. Fiol, and O. Serra, On Cayley line digraphs, Discrete Mat. 138 (1995), no. 1, 147–159.
• [3] D. Buset, M. El Amiri, G. Erskine, M. Miller, and H. Perez-Ros ´ es, A revised Moore bound ´ for mixed graphs, Discrete Math. 339 (2016), no. 8, 2066–2069.
• [4] D. Buset, N. Lopez, 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. Dalfo, A new general family of mixed graphs, ´ Discrete Appl. Math 269 (2019), 99–106.
• [6] C. Dalfo, M. A. Fiol, and N. L ´ opez, Sequence mixed graphs, ´ Discrete Appl. Math. 219 (2017), 110–116.
• [7] C. Dalfo, M. A. Fiol, and N. L ´ opez, On bipartite mixed graphs, ´ J. Graph Theory 89 (2018), no. 4, 386–394.
• [8] C. Dalfo, M. A. Fiol, and N. L ´ opez, An improved Moore bound for mixed graphs and an ´ optimal case with diameter three, Discrete Math. 341 (2018), 2872–2877.
• [9] G. Erskine, Mixed Moore Cayley graphs, J. Intercon. Networks 17, no. 03n04, (2017) 1741010.
• [10] M. L. Fiol, M. A. Fiol, and J. L. A. Yebra, When the arc-colored line digraph of a Cayley colored digraph is again a Cayley colored digraph, Ars Combin. 34 (1992), 65–73.
• [11] 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.
• [12] A. L. Gavrilyuk, M. Hirasaka, and V. Kabanov, A note on Moore Cayley digraphs, Graphs Combin. 37 (2021) 1509–1520.
• [13] A. J. Hoffman and M. H. McAndrew, The polynomial of a directed graph, Proc. Amer. Math. Soc. 16 (1965), 303–309.
• [14] L. K. Jørgensen, New mixed Moore graphs and directed strongly regular graphs, Discrete Math. 338 (2015), 1011–1016.
• [15] N. Lopez and J. M. Miret, On mixed almost Moore graphs of diameter two, ´ Electron. J. Combin. 23(2) (2016), 1–14.

• [16] N. Lopez, J. M. Miret, and C. Fern ´ andez, Non existence of some mixed Moore graphs of ´ diameter 2 using SAT, Discrete Math. 339 (2016), no. 2, 589–596.
• [17] N. Lopez, H. P ´ erez-Ros ´ es, and J. Pujol ´ as, Mixed Moore Cayley graphs, ` Electron. Notes Discrete Math. 46 (2014), 193–200.
• [18] M. Miller and J. Sir ˇ a´n, Moore graphs and beyond: A survey of the degree/diameter problem, ˇ Electron. J. Combin. 20(2) (2013), #DS14v2.
• [19] M. H. Nguyen, M. Miller, and J. Gimbert, On mixed Moore graphs, Discrete Math. 307 (2007), 964–970.
• [20] 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.
• [21] J. Tuite and G. Erskine, On networks with order close to the Moore bound, Graphs Combin. 38 143 (2022).