Electronic Journal of Graph Theory and Applications

Anita Abildgaard Sillasen

Department of Mathematical Sciences, Aalborg University, Denmark anitasillasen@gmail.com

The degree/diameter problem for directed graphs is the problem of determining the largest possible order for a digraph with given maximum out-degree d and diameter k. An upper bound is given by the Moore bound \(M(d,k) = \sum_{i=0}^k d^i\) and almost Moore digraphs are digraphs with maximum out-degree d, diameter k and order M(d,k) - 1.

In this paper we will look at the structure of subdigraphs of almost Moore digraphs, which are induced by the vertices fixed by some automorphism \(\varphi\). If the automorphism fixes at least three vertices, we prove that the induced subdigraph is either an almost Moore digraph or a diregular k-geodetic digraph of degree \(d' \le d-2\), order M(d',k)+1 and diameter k+1.

As it is known that almost Moore digraphs have an automorphism r, these results can help us determine structural properties of almost Moore digraphs, such as how many vertices of each order there are with respect to r. We determine this for d=4 and d=5, where we prove that except in some special cases, all vertices will have the same order.

\(\textit{Keywords}: \ \textit{k}\text{-geodetic digraph}; \ \textit{Moore digraph}; \ \textit{the degree/diameter problem}\)

Mathematics Subject Classification: 05C12, 05C20, 05C75

DOI: 10.5614/ejgta.2015.3.1.1

Received: 27 December 2013, Revised: 21 July 2014, Accepted: 09 October 2014.

1. Introduction

Let G be a digraph and u be a vertex of maximum out-degree d in G, and let \(n_i\) denote the number of vertices in distance i from u. Then, we have \(n_i \leq d^i\) for \(i = 0, 1, \ldots, k\), and thus the order n of G is bounded by

\[n = \sum_{i=0}^{k} n_i \le \sum_{i=0}^{k} d^i.\] (1)

If equality is obtained in (1) we say that G is a Moore digraph of degree d and diameter k, and the right-hand side of (1) is called the Moore bound denoted by \(M(d,k) = \sum_{i=0}^k d^i\). Moore digraphs are known to be diregular and exist only when d=1 (cycles of length (k+1)) or k=1 (complete digraphs with order d+1), see [6] or [12]. So we are interested in knowing how close the order can get to the Moore bound for d>1 and k>1. Let G be a digraph of maximum outdegree d, diameter k and order \(M(d,k)-\delta\), then we say G is a \((d,k,-\delta)\)-digraph or alternatively a (d,k)-digraph of defect \(\delta\). When \(\delta < M(d,k-1)\) we have out-regularity, see [5], whereas in general it is not known if we also have in-regularity. Of special interest is the case \(\delta=1\), and a (d,k,-1)-digraph is also denoted as an almost Moore digraph. Almost Moore digraphs do exist for k=2 as the line digraphs of \(K_{d+1}\) for any \(d\geq 2\), see [9], whereas (2,k,-1)-digraphs for k>2, (3,k,-1)-digraphs for k>2, (d,3,-1)-digraphs for d>1 and (d,4,-1)-digraphs for d>1 do not exist, see [10], [5], [7] and [8]. We do know that almost Moore digraphs are diregular for d>1 and k>1, see [11].

In the last section of the paper, we will be needing the following theorem which summarises some of the above results.

Theorem 1.1 ([10],[5]). Almost Moore digraphs of degree 2 and 3 and diameter k > 2 do not exist.

Furthermore, almost Moore digraphs satisfies the following properties, where a \(\leq k\)-walk is a walk of length at most k.

Lemma 1.1 ([4]). Let G be an almost Moore digraph, then

• (i) for each pair of vertices \(u, v \in V(G)\) there is at most one < k-walk from u to v,
• (ii) for every vertex \(u \in V(G)\) there exist a unique vertex r(u) such that there are two \(\leq k\)-walks from u to r(u).

The mapping \(r: V(G) \mapsto V(G)\) is in fact an automorphism, see [4] and thus the two \(\leq k\)-walks from u to r(u) are internally disjoint. The vertex r(u) is said to be the repeat of u. If we have u = r(u), thus u has order 1 with respect to r, u is said to be a selfrepeat. If there is a selfrepeat in G, then there are exactly k selfrepeats, which lie on a k-cycle, see [3].

In this paper we will give some conditions for the existence of an almost Moore digraph G with respect to some automorphism \(\varphi:V(G)\mapsto V(G)\). These results can then be used to investigate the orders of the vertices with respect to the automorphism r. Before stating the core result of this paper, we will introduce another type of digraph which shows to be important when characterizing induced subdigraphs of almost Moore digraphs.

Let D be a digraph such that for each pair of vertices u, v ∈ V (D) we have at most one ≤ kwalk from u to v, then we say D is k-geodetic. Let u be a vertex of minimum out-degree d, and let nⁱ be the number of vertices in distance i from u for i = 0, 1, . . . , k. Then, nⁱ ≥ d i and the order n of D is bounded by

\[n \ge \sum_{i=0}^{k} n_i \ge \sum_{i=0}^{k} d^i.\] (2)

Notice that the right-hand side is the Moore bound, M(d, k) and that the diameter for a k-geodetic digraph is at least k. As we already know, Moore digraphs exist only for d = 1 or k = 1, we wish to know how close the order of a k-geodetic digraph can get to the Moore bound. By a (d, k, ) digraph we understand a k-geodetic digraph of minimum out-degree d and order M(d, k) + . Alternatively we say that we have a (d, k)-digraph of excess . The first case which is interesting is when = 1. A (d, k, 1)-digraph has diameter k + 1, and for each vertex u there is exactly one vertex, the outlier o(u) such that dist(u, o(u)) = k + 1, see [13].

A (d, k, 1)-digraph is diregular if and only if the mapping o : V (D) 7→ V (D) is an automorphism, see [13]. From [13] we also have the following theorem.

Theorem 1.2 ([13]). No diregular (2, k, 1)-digraphs exist for k > 1.

2. Results

For simplicity, we will, in the remaining part of this paper, let a (d, k, −1)-digraph (almost Moore digraphs) denote any digraph which has degree d > 0, diameter k > 0 and order M(d, k)− 1, thus we will let k-cycles be included in this class. Similarly, a (d, k, 1)-digraph will denote any k-geodetic digraph of minimum out-degree d > 0 and order M(d, k) + 1.

The scope of this paper is to prove the following theorem.

Theorem 2.1. Let G be an almost Moore digraph of degree d ≥ 4 and diameter k ≥ 3 and let H be a subdigraph induced by the vertices which are fixed by some automorphism ϕ : V (G) 7→ V (G). Then, H is either

• (i) the empty digraph,
• (ii) two isolated vertices,
• (iii) an almost Moore digraph of degree d ⁰ ≤ d and diameter k, or
• (iv) a diregular (d 0 , k, 1)-digraph where d ⁰ ≤ d − 2.

In the remaining part of this paper we will assume G to be an almost Moore digraph of degree d ≥ 4 and diameter k ≥ 3, and H to be a subdigraph of G induced by the fixpoints of some automorphism ϕ : V (G) 7→ V (G).

We start by stating some properties of the fixpoints of G.

Lemma 2.1. Let u and v be fixpoints of G with respect to the automorphism ϕ, then

• (i) r(u) is a fixpoint,
• (ii) if there is a ≤ k-walk P from u to v and v 6= r(u), all vertices w ∈ P are fixpoints,

• (iii) if v = r(u) and P and Q are the two \(\leq k\)-walks from u to v, either all internal vertices on P and Q are fixpoints, or none of them are. Furthermore, if dist(u, r(u)) < k, then all vertices on P and Q are fixpoints.
• Proof. (i) We know there are two \(\leq k\)-walks, P and Q, from u to r(u). Now, \(\varphi(P)\) and \(\varphi(Q)\) are two \(\leq k\)-walks from u to \(\varphi(r(u))\), and hence \(\varphi(r(u))\) is a repeat of u. As u only has one repeat, the statement follows.
  • 1. Let P be the unique \(\leq k\)-walk from u to v. Then, \(\varphi(P)\) will also be a \(\leq k\)-walk from u to v, and hence \(P = \varphi(P)\).
  • (ii) Assume not all vertices on the \(\leq k\)-walk P are fixpoints, hence there exists a vertex \(w \in P\) such that \(w \neq \varphi(w)\) and thus \(\varphi(P) \neq P\) is also a \(\leq k\)-walk from u to v = r(u). As there are only two \(\leq k\)-walks from u to v = r(u), we must have \(\varphi(P) = Q\) and thus none of the internal vertices of P are fixpoints, as P and Q are internally disjoint. Now if dist(u, r(u)) < k, then P and Q are obviously of different length, so we must have all vertices on P and Q as fixpoints.

Corollary 2.1. Let \(\varphi\) be an automorphism of G, then all \(\leq k\)-walks among the fixpoints of \(\varphi\) in G are preserved to H, except for possibly the k-walks from a vertex to its repeat.

Notice, that if u and v are selfrepeats fixed by \(\varphi\), then there are exactly d internally disjoint \(\leq (k+1)\)-walks from u to v, \((u,u_i,\ldots,v_i,v)\) for \(i=1,2,\ldots,d\). Hence if the order of \(u_i\) with respect to \(\varphi\) is p, and the order of \(v_i\) with respect to \(\varphi\) is q, then \((u,u_i=\varphi^p(u_i),\ldots,\varphi^p(v_i),v)\) and \((u,u=\varphi^q(u_i),\ldots,v_i=\varphi^q(v_i),v)\) are both \(\leq (k+1)\)-walks, and thus we must have p=q. Said in another way, the permutation cycles with respect to some automorphism \(\varphi\) of the vertices in \(N^+(u)\) and \(N^-(v)\) are the same when u and v are selfrepeats.

The following lemma is a more general result than that of [2].

Lemma 2.2. If G has a selfrepeat which is fixed by \(\varphi\), then H is an almost Moore digraph with selfrepeats of degree \(d' \leq d\) and diameter k.

Proof. Let \(z = r(z) = \varphi(z)\), then according to Lemma 2.1 we must have all vertices on the two \(\leq k\)-walks from z to r(z) as fixpoints, and all the selfrepeats lie on the non-trivial walk from z to z, so H contains a k-cycle.

Notice that \(d_H^+(z)=d_H^-(z)=d'\leq d\) for all \(z=r(z)\in V(H)\), as the permutation cycles in \(N^+(z)\) and \(N^-(z)\) are the same. Now, if we have a vertex \(u=\varphi(u)\neq r(u)\), then we can pick a selfrepeat z such that \(r(u)\notin N^-(z)\), as otherwise we would have \(r(u)\in N^-(z')\) for all selfrepeats z' of G, and therefore r(r(u)) would be a selfrepeat, a contradiction as u is not a selfrepeat. Thus for this u and z we have d internally disjoint \(\leq (k+1)\)-walks \((u,u_i,\ldots,z_i,z)\) in G. Then, d' of the internally disjoint \(\leq (k+1)\)-walks from u to z will also be in H, due to Lemma 2.1, and thus \(d^+(u)\geq d'\). Assume that \(d^+(u)>d'\), then there exists a \(j\in\{1,2,\ldots d\}\) such that \(u_j=\varphi(u_j)\) and \(z_j\neq\varphi(z_j)\). But then \((u_j,\ldots,z_j,z)\) and \((u_j,\ldots,\varphi(z_j),z)\) are two distinct \(\leq k\)-walks from \(u_j\) to z, a contradiction as z is a selfrepeat.

So H is a diregular digraph of degree d'. Now, assume H has diameter k+1, this implies that there exists a vertex v such that \(dist_H(v,r(v))=k+1\) thus the order of H is \(n=1+d'+d'^2+\ldots+d'^k+1=M(d',k)+1\), according to Corollary 2.1. However, looking at a selfrepeat \(z\in H\), we get the order as \(n=1+d'+d'^2+\ldots+d'^k-1=M(d',k)-1\), a contradiction.

So H must be diregular with degree \(d' \leq d\), diameter k and its order must be M(d, k) - 1, hence it is an almost Moore digraph with selfrepeats, as the girth of H is k.

Lemma 2.3. Let \(\varphi\) fix at least three vertices, then H is diregular of degree d' and either

• (i) H is an almost Moore digraph of degree \(d' \leq d\) and diameter k, or
• (ii) H is a (d', k, 1)-digraph of degree \(d' \le d 2\).

Proof. If \(\varphi\) fixes a selfrepeat, then we have the first case of the statement according to Lemma 2.2. Thus we can assume \(\varphi\) does not fix any selfrepeats.

Let u and v be any two fixed vertices in G, thus they are not selfrepeats, and let \(N^+(u) = \{u_1, u_2, \ldots, u_d\}\) and \(N^-(v) = \{v_1, v_2, \ldots, v_d\}\). Assume \(r(u) \neq v_j\) for \(j = 1, 2, \ldots, d\). Then, in G we have internally disjoint \(\leq (k+1)\)-walks \((u, u_i, \ldots, v_i, v)\) for \(i = 1, 2, \ldots, d\). As r is an automorphism, we get \(r(u_i) \neq v\) for \(i = 1, 2, \ldots, d\). Now, we have \(u_i = \varphi(u_i)\) if and only if \(v_i = \varphi(v_i)\) due to Lemma 2.1, hence \(d_H^+(u) = d_H^-(v)\). As we could have v = r(u), we see that each vertex in H is balanced, as \(d^+(u) = d^+(r(u))\) and \(d^-(u) = d^-(r(u))\).

Now, assume H is not diregular, thus for each vertex \(u \in V(H)\) we must have a vertex \(v \in N^+(r(u)) \cap V(H)\) such that \(d_H^+(u) \neq d_H^-(v)\). Let \(u \in V(G)\) be a vertex of minimum degree \(d_1 \leq d\) in H, and let \(v \in V(H)\) be a vertex with \(d_H^-(v) > d_1\). Then, \(d_H^-(v) = d_1 + 2\) as we must have \(v \in N^+(r(u))\) with \(dist_H(u,r(u)) = k+1\) and \(dist_H(r^-(v),v) \leq k\). But then there must be at most \(d_1\) vertices of degree different from \(d_1\) in H and at most \(d_1 + 2\) vertices of degree different from \(d_1 + 2\), hence \(|V(H)| \leq d_1 + (d_1 + 2)\). This is a contradiction to the fact that \(|V(H)| \geq d_1 + d_1^2 + \ldots + d_1^k\) as the diameter of H is at least \(k \geq 3\). So, obviously H is diregular. If dist(u,r(u)) = k+1, then each vertex in H must have at least two out-neighbors of order two with respect to \(\varphi\) and thus the statement follows. \(\square\)

Theorem 2.1 now follows directly from Lemmas 2.2 and 2.3.

3. Almost Moore digraphs of degree 4 and 5

In this section we will look at almost Moore digraphs of degree 4 and 5 and specify the order of the vertices with respect to the automorphism r.

Lemma 3.1. Let \(u \in V(G)\) be a vertex with \(\varphi(u) = u \neq r(u)\), then if H is two isolated vertices or has diameter (k+1) we must have two vertices in \(N_G^+(u)\) which have order 2 with respect to \(\varphi\).

Proof. In G we have two \(\leq k\)-paths, P and Q from u to r(u). If H is either two isolated vertices or has diameter k+1, we must have that the internal vertices on P and Q are not in H. Thus, \(\varphi(P)=Q\) and \(\varphi(Q)=P\), and hence \(\varphi^2(v)=v\) and \(\varphi(v)\neq v\) for all internal vertices v on P and Q.

The following theorem is a more general result than that of [1] and [2].

Theorem 3.1. Let G be an almost Moore digraph of degree 4, then the vertices of G have orders with respect to the automorphism r according to one of the following:

• (i) there are k vertices of order 1 and M(4, k) − 1 − k of order 3, or
• (ii) all vertices are of the same order p ≥ 2.

Proof. Assume throughout that not all vertices are of the same order. Let u be a vertex of G of the smallest order p with respect to r in G. Let N ⁺(u) = {u1, u2, u3, u4}, then we can split N ⁺(u) into permutation cycles with respect to r p in one of the following ways: (u1)(u2)(u3, u4), (u1)(u2, u3, u4), (u1, u2, u3, u4) or (u1, u2)(u3, u4). Notice however that the splitting (u1)(u2)(u3, u4) is not possible, as there according to Theorem 2.1 where ϕ = r ^p would exist a (2, k, −1)- or (2, k, 1)-digraph as an induced subdigraph of G, a contradiction to Theorems 1.1 and 1.2.

First assume there is a vertex u of order 1, thus u is a selfrepeat and hence there are exactly k vertices of order 1 inducing a k-cycle in G. Thus among the above ways of having permutation cycles, the only possibility is (u1)(u2, u3, u4). Then, all vertices which are not selfrepeats must have order 3 according to Lemma 2.2 by letting ϕ = r 3 .

Now assume u ∈ V (G) has the smallest possible order p ≥ 2, then according to Lemma 3.1 the only possible permutation cycles are (u1, u2)(u3, u4). In turn, this is only possible if p = 2, as there will always be at least p vertices of order p in G.

Thus G will contain M(4, k) − 3 vertices of order 4, thus 4 should divide M(4, k) − 3. But in fact

\[M(4,k) - 3 \equiv -2 + 4 + 4^2 + \dots 4^k \equiv 2 \mod 4\],

a contradiction.

Theorem 3.2. Let G be an almost Moore digraph of degree 5, then the vertices of G have orders with respect to the automorphism r according to one of the following:

• (i) there are M(3, k) + 1 vertices of order p ≥ 2 and M(5, k) − M(3, k) − 2 of order 2p
• (ii) there are k + 2 vertices of order p ≥ 2 and M(5, k) − 3 − k of order 2p
• (iii) there are k vertices of order 1 and either M(5, k) − 1 − k of order 2 or M(5, k) − 1 − k of order 4
• (iv) all vertices are of the same order p ≥ 2.

Proof. Assume throughout that not all vertices are of the same order. Let u be a vertex of G of the smallest order p. Let N ⁺(u) = {u1, u2, u3, u4, u5}, then we can split N ⁺(u) into permutation cycles with respect to r p in one of the following ways: (u1)(u2, u3, u4, u5), (u1)(u2)(u3)(u4, u5) or (u1)(u2, u3)(u4, u5) due to Lemma 3.1 and Theorems 1.1 and 1.2.

If the permutation cycles are (u1)(u2, u3, u4, u5), then due to Lemma 3.1 we must have u is a selfrepeat, hence there is k vertices of order 1 and M(5, k) − k − 1 of order 4. If instead the permutation cyles are (u1)(u2, u3)(u4, u5), then we could have k vertices of order 1 and M(5, k)− k − 1 of order 2 or k + 2 vertices of order p ≥ 2 and M(5, k) − k − 3 of order 2p.

Finally, if the permutation cycles are (u1)(u2)(u3)(u4, u5), then if ϕ = r p , we would have H to be either a (3, k, −1)-digraph or a (3, k, 1)-digraph. But (3, k, −1)-digraphs do not exist according

to Theorem 1.1, thus we must have M(3, k) + 1 vertices of order p ≥ 2 and M(5, k)−M(3, k)−2 of order 2p.

Acknowledgements

The work was funded by Prof. Carsten Thomassen's Grants 0602-01488B from The Danish Council for Independent Research | Natural Sciences.

References

• [1] Edy Tri Baskoro and Amrullah, Almost Moore digraphs of degree 4 without selfrepeats, Journal of the Indonesian Mathematical Society (MIHMI) 8(1) (2002), 51–60.
• [2] E.T. Baskoro, Y.M. Cholily and M. Miller, Enumerations of vertex orders of almost Moore digraphs with selfrepeats, Discrete Mathematics 308 (2008), 123–128.
• [3] Edy Tri Baskoro, Mirka Miller and Jan Plesn ´ ´ık, On the structure of digraphs with order close to the Moore bound, Graphs and Combinatorics 14(2) (1998), 109–119.
• [4] Edy Tri Baskoro, Mirka Miller, Jan Plesn ´ ´ık and Stefan Zn ˇ am, Digraphs of degree 3 and order ´ close to the Moore bound, J. Graph Theory 20(3) (1995), 339–349.
• [5] Edy Tri Baskoro, Mirka Miller, Jozef Sir ˇ a´n and Martin Sutton, Complete characterization of ˇ almost Moore digraphs of degree three, J. Graph Theory 48(2) (2005), 112–126.
• [6] W.G. Bridges and S. Toueg, On the impossibility of directed Moore graphs, J. Combin. Theory, Series B 29(3) (1980), 339–341.
• [7] J. Conde, J. Gimbert, J. Gonsalez, J.M. Miret and R. Moreno, Nonexistence of almost Moore ´ digraphs of diameter three, Electron. J. Combin. 15 (2008), #R87.
• [8] , J. Conde, J. Gimbert, J. Gonsalez, J.M. Miret and R. Moreno, Nonexistence of almost Moore ´ digraphs of diameter four, Electron. J. Combin. 20(1) (2013), #P75.
• [9] Miguel Angel Fiol, J. Luis A. Yebra, and Ignacio Alegre de Miquel, Line digraph iterations and the (d, k) digraph problem, IEEE Trans. Computers 33(5) (1984), 400–403.
• [10] Mirka Miller and Ivan Fris, Maximum order digraphs for diameter 2 or degree 2, Pullman Volume of Graphs and Matrices, Lecture Notes in Pure and Applied Mathematics 139 (1992), 269–278.
• [11] Mirka Miller, Joan Gimbert, Jozef Sir ˇ a´n and Slamin, Almost Moore digraphs are diregular, ˇ Discrete Mathematics 218(1-3) (2000), 265–270.
• [12] J. Plesn´ık and S. Zn ˇ am, Strongly geodetic directed graphs, ´ Acta Fac. Rerum Natur. Univ. Comenian., Math. Publ. 23 (1974), 29–34.
• [13] Anita Abildgaard Sillasen, On k-geodetic digraphs with excess one, Electronic Journal of Graph Theory and Applications 2(2) (2014), 150–159.