Anita Abildgaard Sillasen
Department of Mathematical Sciences, Aalborg University, Denmark
anitasillasen@gmail.com
A k-geodetic digraph G is a digraph in which, for every pair of vertices u and v (not necessarily distinct), there is at most one walk of length ≤ k from u to v. If the diameter of G is k, we say that G is strongly geodetic. Let N(d, k) be the smallest possible order for a k-geodetic digraph of minimum out-degree d, then N(d, k) ≥ 1 + d + d 2 + . . . + d k = M(d, k), where M(d, k) is the Moore bound obtained if and only if G is strongly geodetic. Thus, strongly geodetic digraphs only exist for d = 1 or k = 1, hence for d, k ≥ 2 we wish to determine if N(d, k) = M(d, k) + 1 is possible. A k-geodetic digraph with minimum out-degree d and order M(d, k) + 1 is denoted as a (d, k, 1)-digraph or said to have excess 1. In this paper, we will prove that a (d, k, 1)-digraph is always out-regular and that if it is not in-regular, then it must have 2 vertices of in-degree less than d, d vertices of in-degree d + 1 and the remaining vertices will have in-degree d. Furthermore, we will prove there exist no (2, 2, 1)-digraphs and no diregular (2, k, 1)-digraphs for k ≥ 3.
Keywords: k-geodetic digraph; Moore digraph; the degree/diameter problem; almost Moore digraph Mathematics Subject Classification : 05C12, 05C20
1. Introduction
A digraph which satisfies that for any two vertices u, v in G, there is at most one walk of length at most k from u to v, is called a k-geodetic digraph. If the diameter of a k-geodetic digraph G is k, we say that G is strongly geodetic.
Let G be a k-geodetic digraph with minimum out-degree d. What is then the smallest possible order, N(d, k), of such a G? Letting ni be the number of vertices in distance i from a vertex v for
Received: 27 December 2013, Revised: 13 September 2014, Accepted: 20 September 2014.
i = 0, 1, 2, . . ., and realizing that ni ≥ d i , we see that a lower bound is given as
\[N(d,k) \ge \sum_{i=0}^{k} n_i \ge \sum_{i=0}^{k} d^i = M(d,k).\] (1)
The right hand side of (1) is the so called Moore bound for digraphs. The Moore bound is an upper theoretical bound for the so called degree/diameter problem, which is the problem of finding the largest possible order of a digraph with maximum out-degree d and diameter k. A digraph with order M(d, k), maximum out-degree d and diameter k is called a Moore digraph. If a k-geodetic digraph has M(d, k) vertices, then it must be strongly geodetic, and therefore a Moore digraph. However, the only Moore digraphs are (k + 1)-cycles (d = 1) and complete digraphs, Kd+1 (k = 1), see [1] or [2], thus for d ≥ 2 and k ≥ 2 we are interested in knowing if the order for a k-geodetic digraph with minimum out-degree d could be M(d, k) + 1. We say that a k-geodetic digraph G of minimum out-degree d and order M(d, k) + 1 is a (d, k, 1)-digraph or that it has excess one.
Notice that (k + 2)-cycles and (k + 1)-cycles with a vertex having an arc to a vertex on the (k + 1)-cycle are (1, k, 1)-digraphs and that complete digraphs Kd+2 with at most one arc from each vertex deleted are (d, 1, 1)-digraphs. In the remaining part of this paper, we will thus assume d ≥ 2 and k ≥ 2.
In this paper, we will specify some further properties of the (d, k, 1)-digraphs, especially we will show that they have diameter k + 1, and that if a (d, k, 1)-digraph is not diregular, then it is out-regular and there will be exactly d vertices of in-degree d + 1, two vertices of in-degree less than d and the remaining vertices will have in-degree d. In the last section, we will show that there exist no (2, 2, 1)-digraphs and no diregular (2, k, 1)-digraphs.
2. Results
Let an i-walk denote a walk of length i and a ≤ i-walk denote a walk of length at most i. Furthermore, let N + i (u) denote the multiset of all vertices which are end vertices in an i-walk starting at the vertex u, notice that N + 0 (u) = {u} and N + 1 (u) = N +(u). Also let T + i (u) = ∪ i j=0N + j (u), thus it is the multiset of all vertices which are end vertices in a ≤ i-walk starting at the vertex u. Notice that for k-geodetic digraphs N + i (u) and T + i (u) are sets when i ≤ k. Looking at (d, k, 1)-digraphs, we will often depict all the ≤ (k + 1)-paths from some arbitrary vertex u, thus the vertices in the multiset T + k+1(u).
The first important result is that a (d, k, 1)-digraph G is in fact out-regular, as if we assume the contrary, that there is a vertex u ∈ V (G) with d +(u) ≥ d + 1, we get that
\[|V(G)| \ge |T_k^+(u)|\] \[= 1 + (d+1) + (d+1)d + (d+1)d^2 + \dots + (d+1)d^{k-1}\] \[= M(d,k) + M(d,k-1),\]
a contradiction as M(d, k − 1) > 1 for k ≥ 2.
An immediate consequence of a (d, k, 1)-digraph being out-regular, is that it has diameter k+1 which follows in the following lemma.
Lemma 2.1. Let G be a (d, k, 1)-digraph, then
- for each vertex u ∈ V (G) there exists exactly one vertex o(u) ∈ V (G) such that dist(u, o(u)) = k + 1,
- for any two vertices, u, v 6= o(u) there is exactly one ≤ k-path from u to v.
Proof. As we know G is out-regular and the order is M(d, k) + 1, the second statement follows. Let u ∈ V (G) be any vertex and let o(u) be the unique vertex not reachable with a ≤ k-path from u, then we just need to prove d −(o(u)) > 0. Assume the contrary, that d −(o(u)) = 0, then o(u) = o(v) for all v ∈ V (G)\{o(u)}. But then G\{o(u)} will be a Moore digraph of degree d ≥ 2 and diameter k ≥ 2, a contradiction. Hence d −(o(u)) > 0 for all u ∈ V (G) and thus dist(u, o(u)) = k + 1.
The unique vertex o(u) with dist(u, o(u)) = k+1 will be called the outlier of u. So a (d, k, 1) digraph is out-regular of out-degree d and has diameter k + 1. Showing that a (d, k, 1)-digraph G is also in-regular is not as straightforward. We will prove that if it is not in-regular, then there are exactly two vertices of in-degree less than d, d vertices of in-degree d + 1 and the remaining vertices are of in-degree d. Let S 0 = {v ∈ V (G)|d −(v) > d} and S = {v ∈ V (G)|d −(v) < d}, then we get the following lemmas and theorem.
Lemma 2.2. Let G be a (d, k, 1)-digraph, then
- |S 0 | ≤ d and d −(v) = d + 1 for all v ∈ S 0 ,
- S 0 ⊆ N +(o(u)) for all u ∈ V (G).
Proof. Assume u ∈ V (G) and v /∈ N +(o(u)), then as u must reach all in-neighbors of v in ≤ k-paths, we must have d +(u) ≥ d −(v). If not, then there will exist an out-neighbor u 0 of u which has two ≤ k-paths to v, a contradiction. Now, if v ∈ N +(o(u)), then u must reach all in-neighbors of v, except o(u), in a ≤ k-path. Thus with the same arguments as before, we must have d +(u) ≥ d −(v) − 1. Thus all vertices in S 0 must have in-degree d + 1 and both statements follows, as |N +(o(u))| = d.
Lemma 2.3. If S 0 6= ∅, then |S 0 | = d.
Proof. As a (d, k, 1)-digraph is out-regular, its average in-degree must be d and thus
\[\sum_{v \in S'} (d^-(v) - d) = \sum_{v \in S} (d - d^-(v)) = |S'|.\]
Now let v ∈ S 0 , then we know |N −(v)| = |N − 1 (v)| = d + 1 and |N − t (v)| ≥ d|N − t−1 (v)| − t for 1 < t ≤ k, where 2 + 3 + . . . + k ≤ |S 0 |. As all vertices in T − k (v) are distinct, it implies that
\[|V(G)| \ge \sum_{i=0}^{k} |N_i^-(v)|.\] (2)
Estimating the above sum, we get a safe lower bound by letting \(\epsilon_2 = |S'|\) and \(\epsilon_t = 0\) for all 3 < t < k, thus
\[\begin{aligned} |V(G)| &\geq 1 + |N^{-}(v)| + |N^{-}_{2}(v)| + |N^{-}_{3}(v)| + \ldots + |N^{-}_{k}(v)| \\ &\geq 1 + (d+1) + ((d+1)d - |S'|)(1 + d + \ldots + d^{k-2}) \\ &= 2 + d + d^{2} + \ldots + d^{k} + (d - |S'|)(1 + d + \ldots d^{k-2}) \\ &= M(d,k) + 1 + (d - |S'|)M(d,k-2). \end{aligned}\]
But as G is a (d, k, 1)-digraph, we have |V(G)| = M(d, k) + 1, which together with the preceding inequality and Lemma 2.2 gives |S'| = d.
As a consequence of the above proof, we have that \(S \subseteq N^-(v)\) for all \(v \in S'\).
Theorem 2.1. Let G be a (d, k, 1)-digraph. If G is not diregular, then we have \(S = \{z, z'\}\) where \(o(u) \in S\) for all \(u \in V(G)\).
Proof. Assume G is not diregular, thus we can assume \(S' = \{u_1, u_2, \ldots, u_d\}\) where \(d^-(u_i) = d+1\) and \(o(u) \in N^-(u_j)\) for all \(u \in V(G)\) and \(j=1,2,\ldots,d\) according to Lemmas 2.2 and 2.3. Moreover, from the proof of Lemma 2.3 we see that \(dist(v,u_i) \leq k\) for all \(v \in G\) and \(i=1,2,\ldots,d\).
Now let \(N^-(u_1)=\{z_1,z_2,\ldots,z_{d+1}\}\) where \(z_1=o(u_1)\). Then \(S'\cap T_{k-1}^-(z_1)=\emptyset\), as otherwise \((z_1,u_j,\ldots,z_1)\) will be a \(\leq k\)-cycle for some \(j=1,2,\ldots,d\). Also, no two vertices \(u_i\) and \(u_j\) can belong to the same \(T_{k-1}^-(z_l)\) for \(1\leq l\leq d+1\), as if they did, \((z_1,u_i,\ldots,z_l)\) and \((z_1,u_j,\ldots,z_l)\) would be two distinct \(\leq k\)-paths. Thus we can assume \(S'\cap T_{k-1}^-(z_l)=\{u_l\}\) for \(1\leq l\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\) and \(1\leq k\leq d\)
Finally we wish to show that \(S = \{z_1, z_{d+1}\}\). Assume the contrary, thus for some \(2 \le l \le d\) we have \(d^-(z_l) < d\) and \(o(u) \ne z_l\) for all \(u \in V(G)\), as \(S \subseteq N^-(u_1)\). But then
\[|V(G)| \le 1 + (d-1)(1+d+d^2+\ldots+d^{k-1}) + 1\]
= \(M(d,k) - M(d,k-1) + 1\)
< \(M(d,k) + 1\)
as \(dist(u_l, z_l) = k - 1\) and \(dist(u_j, z_l) \ge k\) for all \(j \ne l\). Thus \(S \subseteq \{z_1, z_{d+1}\}\) and as \(\sum_{v \in S'} (d^-(v) - d) = d = \sum_{v \in S} (d - d^-(v))\) and \(d^-(u) > 0\) for all \(u \in V(G)\) the result follows.
If G is diregular, we get the following useful lemma.
Lemma 2.4. Let G be a diregular (d, k, 1)-digraph, then the mapping \(o : V(G) \mapsto V(G)\) is an automorphism.
Proof. Let A be the adjacency matrix of G, then due to the properties of G we get
\[I + A + A^2 + \ldots + A^k = J - P,\] (3)
where J is the matrix with all entries equal to 1 and P is a permutation matrix with entry Pij = 1 if o(i) = j and Pij = 0 otherwise.
Now, as we know G is diregular, we know that AJ = JA, and as the left hand side of (3) is a polynomial in A, we must also have P A = AP, thus o is an automorphism.
Notice that if G is diregular there will be exactly d paths of length k + 1 from a given vertex u to o(u), as all u's out-neighbors must reach o(u) in k-paths and if there were more than d paths of length k + 1, one of u's out-neighbors would have more than one ≤ k-path to o(u), a violation of the definition of (d, k, 1)-digraphs.
3. (2, k, 1)-digraphs
In this section we will assume d = 2 and prove the non-existence of (2, 2, 1)-digraphs and diregular (2, k, 1)-digraphs.
Theorem 3.1. There are no (2, 2, 1)-digraphs.
Proof. Assume G is a (2, 2, 1)-digraph, then it has 8 vertices and we can depict the relationship between the vertices in T + 3 (1) as in Fig. 1, where we can see o(1) = 8.
Figure 1. T + 3 (1).
Assume G is not diregular, then we know from Theorem 2.1 that d −(8) = 1 and there exist another vertex z ∈ V (G) with d −(z) = 1 and o(3) = o(6) = z. Furthermore we know N +(8) = N +(z) = {u1, u2} with d −(ui) = 3 for i = 1, 2. Notice that 6 ∈ { / u1, u2}, as otherwise G would contain a 2-cycle, (6, 8, 6). As the diameter of G is 3, we must have dist(2, 6) = 2 for 2 to reach 8 and thus o(2) = 8. Assume without loss of generality that 6 ∈ N +(4). Then for 5 to reach 8 we must have 3 ∈ N +(5), as N −(6) = {3, 4} and 4 ∈/ N +(5), as otherwise (2, 4) and (2, 5, 4) will be two distinct ≤ 2-paths. The only vertices which 2 cannot reach are 1 and 7. If 7 ∈ N +(5) we have (5, 7) and (5, 3, 7) as ≤ 2-paths, which is a contradiction. If instead 1 ∈ N +(5) then we have the ≤ 2-paths (5, 1, 3) and (5, 3) another contradiction.
Now assume that G is diregular and recall that then o is an automorphism, thus we can assume 8 ∈ N +(5) as o(2) 6= 8. Then, we see that o(2) 6= 6, as otherwise there would be a 2-cycle (6, 8, 6)
as o is an automorphism, a contradiction. So there will be a \(\leq\) 2-path from 2 to 6, but \(6 \notin N^+(5)\) as otherwise there are two \(\leq\) 2-paths from 5 to 8, namely (5,8) and (5,6,8). Thus \(6 \in N^+(4)\), and in the same manner we see that \(5 \in N^+(7)\). Let u and v be the other out-neighbor of 4 and 5 respectively, and w and z the other out-neighbor of 6 and 7 respectively.
As 2 has to reach vertex 1, 3 and 7 and at most one of them can be the outlier of 2, we must have \(u \in \{1,7\}\) and \(v \in \{1,3\}\), as if u=3 there will exist two \(\leq\) 2-paths from 4 to 6, namely (4,6) and (4,3,6) and if v=7 we will get a 2-cycle, (7,5,7). Similar we see \(z \in \{1,4\}\) and \(w \in \{1,2\}\).
Now assume o(2)=1, hence \(o(3)\neq 1\) and (o(1),o(2))=(8,1) is an arc. Then u=7 and v=3, and as o is an automorphism, we must have z=1, as if w=1 we will have the two \(\leq\) 2-paths, (6,1) and (6,8,1). But then (7,1,3) and (7,5,3) are both 2-paths from 7 to 3, a contradiction.
Instead assume o(2)=3, thus u=7 and v=1 and (o(1),o(2))=(8,3) is an arc. But then (5,1,3) and (5,8,3) are both 2-paths from 5 to 1. So we can safely assume o(2)=7, thus u=1 and v=3, but then (5,3,7) and (5,8,7) are both 2-paths from 5 to 7, another contradiction.
Theorem 3.2. No diregular (2, k, 1)-digraph exists for \(k \geq 2\).
Proof. Due to Theorem 3.1 we can assume k>2 and we label the vertices in \(T_{k+1}^+(1)\) as in Fig. 2. First of all, notice that for all \(u\in V(G)\) we obviously have \(o(u)\notin T_k^+(u)\), so we must have \(o(2)\in T_{k-1}^+(3)\cup\{1\}\). We also see that \(o(2)\notin T_{k-2}^+(6)\), as otherwise there will be two \(\leq k\)-paths from 6 to o(2), the one in \(T_{k-2}^+(6)\) and \((6,12,\ldots,3\cdot 2^{k-1},2^{k+1}=o(1),o(2))\), a contradiction.
Figure 2. \(T_{k+1}^+(1)\).
Now, let \(A=N_{k-1}^+(4)\) and \(B=N_{k-1}^+(5)\backslash\{2^{k+1}\}\), so \(|A|=2^{k-1}\) and \(|B|=2^{k-1}-1\). Then we will look at how \((\{1\}\cup T_{k-1}^+(3))\backslash o(2)\) is distributed on A and B. For any arc (u,v) in G, we must have that u and v will not both be in A and not both in B, as otherwise there would be two \(\leq k\)-paths from either 4 or 5 to v. We observe that \(3\cdot 2^{k-1}\notin B\), as otherwise there would be two \(\leq k\)-paths from 5 to \(2^{k+1}\), namely \((5,11,\ldots 3\cdot 2^{k-1}-1,2^{k+1})\) and \((5,\ldots ,3\cdot 2^{k-1},2^{k+1})\). So we
must have 3 · 2 k−1 ∈ A, 3 · 2 k−2 ∈ B, 3 · 2 k−3 ∈ A, and so on, until we reach vertex 6. This implies that N + k−2 (6) ∈ A, N + k−3 (6) ∈ B, N + k−4 (6) ∈ A and so on, until we get either 6 ∈ A if k is even or 6 ∈ B if k is odd.
Let a = |A ∩ T + k−2 (6)| and b = |B ∩ T + k−2 (6)|, so a + b = 2k−1 − 1. Now, if k is even we let
\[a_e = a = \sum_{i=0}^{\frac{k}{2}-1} 2^{2i} = -\frac{1}{3} + \frac{2}{3} \cdot 2^{k-1}\]
and
\[b_e = b = \sum_{i=0}^{\frac{k}{2}-2} 2^{2i+1} = -\frac{2}{3} + \frac{1}{3} \cdot 2^{k-1}.\]
Similarly, if k is odd we let
\[a_o = a = \sum_{i=0}^{\frac{k-3}{2}} 2^{2i+1} = -\frac{2}{3} + \frac{2}{3} \cdot 2^{k-1}\]
and
\[b_o = b = \sum_{i=0}^{\frac{k-3}{2}} 2^{2i} = -\frac{1}{3} + \frac{1}{3} \cdot 2^{k-1} = \frac{1}{2} a_o.\]
We start by assuming that o(2) = 1, then if k is even we see that vertex 3 must be in B, so 7 ∈ A, {14, 15} ⊆ B,. . ., N + k−2 (7) ⊆ A. Thus
\[|A| = 2 \cdot a_e = 2\left(-\frac{1}{3} + \frac{2}{3} \cdot 2^{k-1}\right) > 2^{k-1}\]
as k > 2, a contradiction. If k is odd, we see that vertex 3 must be in A, so 7 ∈ B, {14, 15} ⊆ A,. . ., N + k−2 (7) ⊆ A, thus
\[|A| = 2a_o + 1 = 2\left(-\frac{2}{3} + \frac{2}{3} \cdot 2^{k-1}\right) + 1 > 2^{k-1}\]
as k > 2, yet a contradiction. So, we know due to symmetry that 1 ∈ { / o(2), o(3)}.
Now, assume that o(2) 6= 3. Then, we know the distribution of all the vertices in T + k−1 (3)∪ {1} except for those in T + i (o(2)), where i is given by dist(3, o(2)) = k − 1 − i. Assume i = 0, thus o(2) ∈ N + k−2 (7), or that N +(o(2)) is in the same set (A or B) as N + k−1−i (6), then we see that |A| ≥ 2a > 2 k−1 , a contradiction. So, we can assume there exist vertices u and v, such that N +(o(2)) = {u, v} ⊆ T + k−2 (7) and that not both u and v are in the same set (A or B) as N + k−1−i (6).
For even i, let ce denote the number of vertices in every second layer of T + i (o(2)) such that N + i (o(2)) is not one of those layers, then
\[c_e = \sum_{j=0}^{\frac{i}{2}-1} |N_{2j+1}^+(o(2))| = 2(1+2^2+\ldots+2^{i-2}) = \frac{2}{3} \cdot 2^i - \frac{2}{3}.\]
Let de denote the number of vertices in the remaining layers, thus
\[d_e = \sum_{j=0}^{\frac{i}{2}-1} |N_{2j+2}^+(o(2))| = 2c_e.\]
For odd i, let co denote the number of vertices in every second layer, where N + i (o(2)) is not one of those layers, thus
\[c_o = \sum_{j=0}^{\frac{i-3}{2}} |N_{2j+2}^+(o(2))| = \frac{1}{3}(2^{i+1} - 1) - 1 = \frac{1}{3} \cdot 2^{i+1} - \frac{4}{3}\]
and the number of vertices in the remaining layers is then
\[d_o = \sum_{j=0}^{\frac{i-1}{2}} |N_{2j+1}^+(o(2))| = 2c_o + 2.\]
We will now count the number of vertices in A depending on whether k and i are even or odd, and which set (A or B) u and v are in, a total of 8 different scenarios. Notice that exactly one of 1 and 3 will be in A. We will obtain contradictions in some of the scenarios and in the remaining we will obtain that o(2) = 7. Thus, we have proved that o(2) ∈ {3, 7}.
If k is even, we get following scenarios:
• i even:
– u, v ∈ A: Then,
\[|A| = 2a_e + 1 + c_e - d_e - 1\] \[= 2\left(-\frac{1}{3} + \frac{2}{3} \cdot 2^{k-1}\right) - c_e\] \[= \frac{2}{3} \cdot 2^k - \frac{2}{3} \cdot 2^i.\]
Now, as we already know |A| = 2k−1 , we must have i = k − 2, and thus o(2) = 7.
– u ∈ A, v ∈ B: Then, half of the vertices in T + i (o(2))\{o(2)}, namely 2 i − 1 vertices, will be in A and the other in B, hence
\[|A| = 2a_e + 1 - d_e - 1 + 2^i - 1\] \[= 2\left(-\frac{1}{3} + \frac{2}{3} \cdot 2^{k-1}\right) - \frac{4}{3}(2^i - 1) + 2^i - 1\] \[= -\frac{1}{3} + \frac{2}{3} \cdot 2^k - \frac{1}{3} \cdot 2^i\]
a contradiction with |A| = 2k−1 .
• i odd:
– u, v ∈ B: Similar to the above argument, we see that
\[\begin{split} |A| &= 2a_e + 1 + c_o - d_o \\ &= 2\left(-\frac{1}{3} + \frac{2}{3} \cdot 2^{k-1}\right) + 1 + c_o - 2c_o - 2 \\ &= -\frac{2}{3} + \frac{4}{3} \cdot 2^{k-1} - \left(\frac{1}{3} \cdot 2^{i+1} - \frac{4}{3}\right) - 1 \\ &= -\frac{1}{3} + \frac{4}{3} \cdot 2^{k-1} - \frac{1}{3} \cdot 2^{i+1}, \end{split}\]
again a contradiction to the fact that |A| = 2k−1 .
– u ∈ A, v ∈ B: We see
\[|A| = 2a_e + 1 + 2^i - 1 - d_o\] \[= 2\left(-\frac{1}{3} + \frac{2}{3} \cdot 2^{k-1}\right) + 1 + 2^i - 1 - \frac{2}{3}(2^{i+1} - 1)\] \[= \frac{2}{3} \cdot 2^k - \frac{1}{3} \cdot 2^i.\]
As |A| = 2k−1 , this implies i = k − 1, but then o(2) = 3, a contradiction to our assumption.
If k is odd we have:
• i even:
– u, v ∈ A: Then,
\[|A| = 2a_o + 1 + c_e - d_e - 1\] \[= 2\left(-\frac{2}{3} + \frac{2}{3} \cdot 2^{k-1}\right) - c_e\] \[= -\frac{2}{3} + \frac{2}{3} \cdot 2^k - \frac{2}{3} \cdot 2^i,\]
yet a contradiction to |A| = 2k−1 .
– u ∈ A, v ∈ B: We see
\[|A| = 2a_o + 1 - d_e - 1 + 2^i - 1\] \[= 2\left(-\frac{2}{3} + \frac{2}{3} \cdot 2^{k-1}\right) - \frac{4}{3}(2^i - 1) + 2^i - 1\] \[= -1 + \frac{2}{3} \cdot 2^k - \frac{1}{3} \cdot 2^i,\]
a contradiction to |A| = 2k−1 and i 6= 0.
• i odd:
– u, v ∈ B: Similarly, we see that
\[\begin{aligned} |A| &= 2a_o + 1 + c_o - d_o \\ &= 2\left(-\frac{2}{3} + \frac{2}{3} \cdot 2^{k-1}\right) + 1 + c_o - 2c_o - 2 \\ &= -\frac{4}{3} + \frac{4}{3} \cdot 2^{k-1} - \left(\frac{1}{3} \cdot 2^{i+1} - \frac{4}{3}\right) - 1 \\ &= -1 + \frac{4}{3} \cdot 2^{k-1} - \frac{1}{3} \cdot 2^{i+1}, \end{aligned}\]
yet another contradiction to the fact that |A| = 2k−1 .
– u ∈ A, v ∈ B: We see
\[|A| = 2a_o + 1 + 2^i - 1 - d_o\] \[= 2\left(-\frac{2}{3} + \frac{2}{3} \cdot 2^{k-1}\right) + 2^i - \frac{2}{3}(2^{i+1} - 1)\] \[= -\frac{2}{3} + \frac{2}{3} \cdot 2^k - \frac{1}{3} \cdot 2^i.\]
Then, we must have k = 3 and i = 1, thus o(2) = 7.
To summarize the above, we have o(2) ∈ {3, 7} and o(3) ∈ {2, 4}. Using similar arguments we observe o(4) ∈ {5, 10}, as (11, . . . , 2 k+1 = o(1), o(2), o(4)) is a k-path. Now, if o(2) = 3 we get o(4) ∈ N +(o(2)) = {6, 7}, but this is a contradiction to our observation. On the other hand, if o(2) = 7 we must have o(4) ∈ {14, 15} again a contradiction.
Acknowledgements
The work was funded by Prof. Carsten Thomassen's Grants 0602-01488B from The Danish Council for Independent Research | Natural Sciences.
References
- [1] W. G. Bridges and Sam Toueg, On the Impossibility of Directed Moore Graphs, Journal of Combinatorial Theory, Series B, 29(3) (1980), 339–341.
- [2] J. Plesn´ık and S. Zn ˇ am, Strongly geodetic directed graphs. ´ Acta Fac. Rerum Natur. Univ. Comenian., Math. Publ. 23 (1974), 29–34.