The (∆, D) and (∆, N) problems in double-step digraphs with unilateral distance

C. Dalfo, M.A. Fiol ´

Departament de Matematica Aplicada IV ` Universitat Politecnica de Catalunya ` Barcelona, Catalonia

{cdalfo,fiol}@ma4.upc.edu

We study the (∆, D) and (∆, N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, the latter obtained by changing the directions of all the arcs.

The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree ∆ and the unilateral diameter D^∗ , whereas the second one (somehow dual of the first) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for infinitely many values of the number of vertices. Moreover, we compute the mean unilateral distance of the digraphs in the families considered.

Keywords: (∆, D) problem, (∆, N) problem, unilateral distance, double-step digraphs Mathematics Subject Classification: 05C20, 05C12

1. Introduction

The (∆, D) and (∆, N) problems have been extensively studied for graphs and digraphs. Miller and Siran [9] wrote a comprehensive survey about these problems. In particular, for the so-called ´ double-step graphs considering the standard diameter, the first problem was solved by Yebra, Fiol, Morillo and Alegre [11], whereas Bermond, Iliades and Peyrat [3], and also Beivide, Herrada,

Received: 8 September 2013, Revised: 14 January 2014, Accepted: 26 January 2014.

Figure 1. Steps of G(N; a, b) (left), and the double-step digraph G(8; 1, 3) (right).

Balcazar and Arruabarrena [2] solved the ´ (∆, N) problem. In the case of the double-step digraphs also with the standard diameter, Morillo, Fiol and Fabrega [10] solved the ` (∆, D) problem and provided some infinite families of digraphs which solve the (∆, N) problem for their corresponding numbers of vertices. Esque, Aguil ´ o and Fiol [5], and Aguil ´ o and Fiol [1] contributed to the ´ second problem with more general results.

Double-step digraphs were proposed and studied as models for the so-called 'local area networks', in which several computers placed at short distances exchange data at very high speed, as explained in Fiol, Yebra, Alegre and Valero [6]. In particular, the delay in the transmission of a message between two nodes is closely related to the minimum number of necessary steps to get their target, that is, the distance between nodes. What allows us to go from the combinatorial formulation (the network structure) to the algebraic one is the representation of each digraph as an 'L-shaped or X-shaped tile' (a planar region), which periodically tessellates the plane by translations (2-dimensional integer lattice). With these geometric forms we can study more easily the properties related to the distance in a digraph, such as its diameter and its mean distance.

In this paper we study the (∆, D^∗ ) and the (∆, N) ^∗ problems for double-step digraphs, where the asterisks indicate that we consider the unilateral distance instead of the standard distance. The former is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by changing the directions of all the arcs.

The plan of the paper is as follows. In the next section we recall the definitions of double-step digraph, unilateral distance, and unilateral diameter. Moreover, we show that if we take the vertices at minimum distance from a given vertex, we obtain an L-shaped or X-shaped tile, depending on whether we consider the standard or the unilateral diameter, respectively. In Section 3, we give the unilateral diameter of double-step digraphs when one step is equal to 1. In Section 4, we solve the (∆, D^∗ ) problem for every value of the unilateral diameter and also the (∆, N) ^∗ problem for infinitely many values of the number of vertices. Finally, in the last section, we derive formulas for computing the mean unilateral distance of the double-step digraphs considered.

2. Preliminaries

We recall the basic definitions and concepts concerning double-step digraphs and unilateral distance, together with their geometric representations.

Figure 2. A generic L-shaped tile (left), and the L-shaped tile of G(8; 1, 3) (right).

2.1. Double-step digraphs

A double-step digraph G(N; a, b) has set of vertices \(\mathbb{Z}_N = \mathbb{Z}/N\mathbb{Z}\) and arcs from every vertex i to vertices \(i+a \mod N\) and \(i+b \mod N\), for \(0 \le i \le N-1\), where a, b are some integers called steps such that \(1 \le a < b \le N-1\). Because of the automorphisms \(i \mapsto i+\alpha\) for \(1 \le \alpha \le N-1\), the double-step digraphs are vertex-transitive. Moreover, they are strongly connected if and only if \(\gcd(N,a,b)=1\). In Fig. 1 we show the steps of a double-step digraph G(N;a,b) and, as an example, G(8;1,3). It is known that the maximum order N of a double-step digraph with diameter k is upper bounded by the Moore-like bound \(N \le M_{DSD}(2,k) = \binom{k+2}{2}\), where the equality would hold if all the numbers ma+nb were different modulo N, with \(m,n \ge 0\) and \(m+n \le k\). In fact, this bound cannot be attained for k > 1. For more details, see Esqué, Aguiló and Fiol [5], Aguiló and Fiol [1], and Fiol, Yebra, Alegre and Valero [6].

Given a double-step digraph G(N;a,b) that is assumed to be strongly connected, consider the plane divided into unitary squares, centered in the integral coordinate points forming a lattice. From a square—or lattice point—labeled with zero, we add \(a \mod N\) when we move horizontally to the right to the next square, and \(b \mod N\) when we move vertically upwards. Then, the plane is covered by integers modulo N, that is, the elements of the cyclic group \(\mathbb{Z}_N\), as shown in Fig. 2 (right) with the example of the digraph G(8;1,3). Note that, in this way, each vertex of a digraph G(N;a,b) is related to a lattice point. Moreover, those at minimum distance from 0 form a 2-dimensional lattice which univocally characterizes the digraph. In turn, such a lattice is determined by a basis of two (integer) vectors \(\mathbf{u} = (\ell, -y)\) and \(\mathbf{v} = (-w, h+y)\), satisfying \(N = \ell(h+y) - wy\) and \(\gcd(\ell,h,w,y) = 1\) (see Figure 3). Now, if we choose any N vertices (squares) with different labels modulo N, we get a tile which periodically tessellates the plane and, in the cases we consider, the dimensions of such a tile are closely related to the entries of the vectors \(\mathbf{u}\), \(\mathbf{v}\). Let us see some useful cases:

• If all the vertices different modulo N are chosen to be at minimum (standard) distance from vertex 0 (this is done by following a simple algorithm that considers the successive diagonals, as is shown again in Fig. 2 (right)), Brawer and Shokley [4] proved that the tiles are always L-shaped tiles characterized by its dimensions \((\ell, h+y, w, y)\), with \(\ell, h+y \geq 1, 0 \leq w \leq \ell\), \(1 \leq y \leq h\), see again Fig. 2 (left), and the corresponding L-basis is \(u = (\ell, -y), v = 0\)

Figure 3. The vectors of an L-basis (left), and the dimensions of an L-shaped form with area N = `h + s (right).

(−w, h + y), as shown in Fig. 3.

• If one of the steps, say a, equals 1, we can choose again an L-shaped tile with dimensions: ` = b, h being the quotient obtained dividing N by `, w = ` − s with s being the remainder of such a division, and y = 1. Then, N = `h + s with 0 ≤ s < ` (see Fig. 3).
• If all the vertices which are distinct modulo N are chosen at minimum unilateral distance (see its definition in Subsection 2.2) from vertex 0 (following again a simple algorithm) we get a kind of X-shaped tile, as shown in Fig. 4. Moreover, in the above case (a = 1), we can 'rebuild' the obtained tile as an L-shaped tile placing the inferior 'half' (without the 0) onto the superior one. (In other words, the vertices at minimum unilateral distance from and to vertex 0 are taken from two different points of the plane representing it.) See again Fig. 4.

Conversely, from a basis u = (`, −y) and v = (−w, h + y) (or 'distribution of zeros') of the lattice with gcd(`, h, w, y) = 1, the steps a and b of the corresponding digraph of N = `(h+y)−wy vertices (or a tile with the same area) can be obtained as the solutions of the following system of equations:

\[\ell a - yb = \alpha N \ (\equiv 0 \mod N),\]
\[-wa + (h+y)b = \beta N \ (\equiv 0 \mod N),\]

which gives

\[a = \alpha(h+y) + \beta y, \qquad b = \alpha w + \beta \ell,\] (1)

where α and β must be chosen so that the condition gcd(N, a, b) = 1 is satisfied. (See Fiol, Yebra, Alegre, and Valero [6] for more details.) For instance, if we apply this method to the example

Figure 4. From X-shaped forms to L-shaped forms (for the case \(s = \ell - 1\)): (a) \(\ell + h\) even, and (b) \(\ell + h\) odd. The squares with an asterisk represent the farthest vertices from 0.

of G(8;1,3) (see again Figs. 1 and 2), the dimensions of the L-shaped tile are \(\ell=3\), h=2, w=y=1. Then, \(a=3\alpha+\beta\) and \(b=\alpha+3\beta\). A good choice is \(\alpha=0\) and \(\beta=1\), which gives the steps a=1 and b=3. More generally, for an L-shaped tile with dimensions \(\ell\), h+y, \(w=\ell-s\) and y=1 (see Fig. 3), we get a=1 and \(b=\ell\), as expected. Observe that the values of the steps a and b are not unique. Indeed, given a feasible pair a,b we obtain an isomorphic digraph with the steps \(\gamma a\), \(\gamma b\) for any integer \(\gamma\) relatively prime to N.

2.2. Unilateral distance

Given a digraph G=(V,A), the unilateral distance between two vertices \(u,v\in V\) is defined as

\[\operatorname{dist}_G^*(u,v) = \min\{\operatorname{dist}_G(u,v),\operatorname{dist}_G(v,u)\} = \min\{\operatorname{dist}_G(u,v),\operatorname{dist}_{\overleftarrow{G}}(u,v)\},\]

where \(\operatorname{dist}_G\) is the standard distance in digraph G and \(\operatorname{dist}_{\overleftarrow{G}}\) is the distance in its converse digraph \(\overleftarrow{G}\), that is, the digraph obtained by changing the directions of all the arcs of G. From this concept, we can define the unilateral eccentricity \(\operatorname{ecc}^*\) from vertex u, the unilateral radius \(r^*\) of G, and the unilateral diameter \(D^*\) of G as follows:

\[\mathrm{ecc}^*(u) = \max_{v \in V} \{ \mathrm{dist}_G^*(u,v) \}, \quad r^* = \min_{u \in V} \{ \mathrm{ecc}^*(u) \}, \quad \text{and} \quad D^* = \max_{u \in V} \{ \mathrm{ecc}^*(u) \}.\]

As an example, if we have \(G = C_N\), the directed cycle on N vertices, then \(r^* = D^* = \lfloor N/2 \rfloor\).

Note that, obviously, these parameters have as lower bounds the ones corresponding to the underlying graph, obtained from digraph G by changing the arcs for edges without direction. Some constructions of general digraphs with large number of vertices given the maximum degree and unilateral diameter (that is, the \((\Delta, D^*)\) problem for digraphs) were proposed by Gómez, Canale and Muñoz [7, 8].

3. The unilateral diameter of double-step digraphs with steps a=1 and \(b=\ell\)

In this section we study the unilateral diameter of the double-step digraphs with a=1 having 'small' b. Although we have not been able to prove that the optimal results can be obtained always

Figure 5. Tessellations for 2s + 1 < ` and 2s + 1 ≥ `

by taking such values of the steps, computational experiments seem to support this claim. In fact, as we see in the next section, this approach allows us to solve the (∆, D^∗ ) problem for every value of D^∗ , and also to solve the (∆, N) ^∗ problem for infinitely many values of N.

As we have already seen, a double-step digraph G(N; 1, b) with N = `h + s and 0 ≤ s < `, can be described by an L-shaped form with dimensions ` = b, h = bN/`c, y = 1, and w = ` − s. See again Fig. 3 (right). In this context we have the following result for the unilateral diameter D^∗ .

Proposition 3.1. For ^{N =} `h+s, where <sup>1</sup> < ` ≤ d√ Ne and 0 ≤ s ≤ `−1, a double-step digraph G(N; a, b) with a = 1 and b = ` has unilateral diameter

\[D^* = \begin{cases} \left\lfloor \frac{\ell + h + s - 1}{2} \right\rfloor & \text{if } 0 \le s \le \ell - 2, \\ \left\lfloor \frac{\ell + h - 1}{2} \right\rfloor & \text{if } s = \ell - 1. \end{cases}\] (2)

Proof. To determine the vertices at minimum unilateral distance from 0, it is useful to divide the L-shaped form into two parts: The left one is an L-tile with left bottom corner (0, 0) and right top (missing) corner (s, h) (both points correspond to vertex 0). The right part is a rectangle R with left bottom corner i = (s + 1, 0) and right top corner j = (` − 1, h − 1) (with basis ` − s − 1 and height h). See Fig. 5 for the cases 2s + 1 < ` and 2s + 1 ≥ ` and compare the two paths to go to equivalent vertices. In both cases, notice that, if h + 1 ≥ s + 1 (a condition that is always fulfilled since s < ` ≤ d√ Ne), the unilateral distances from 0 to i and to j are both s+1. As a consequence, the farthest vertices from 0 are in (one or two) NW-SE diagonals of R or, equivalently, the same diagonals of the rectangle R<sup>0</sup> with basis ` 0 and height h 0 shown in Fig. 6, in grey dashed lines, with

Figure 6. Some cases of Proposition 3.1.

values

\[\ell' = \begin{cases} \ell + s + 1 & \text{if } 0 \le s \le \ell - 2, \\ \ell & \text{if } s = \ell - 1. \end{cases}\] \[h' = \begin{cases} h & \text{if } 0 \le s \le \ell - 2, \\ h + 1 & \text{if } s = \ell - 1. \end{cases}\]

Consequently, the unilateral diameter \(D^*\) turns out to be

\[D^* = \left| \frac{\ell' + h'}{2} - 1 \right|,\]

whence we obtain the claimed result.

As an example, in Fig. 7, we show some of the possible L-shaped forms for N=48, where the minimum unilateral diameter is 6, corresponding to the L-shaped form with \(\ell=6\), h=8 and s=0, that is, the double-step digraph G(48;1,6); or \(\ell=7\), h=8 and s=6 giving G(48;1,8). In Table 1, there are the unilateral diameters corresponding to all the possible values of \(\ell\) for N=48 and N=49 (the values in grey do not satisfy \(1<\ell\le \lceil \sqrt{N}\rceil\)). All these values are represented in Fig. 8.

If there is not restriction for the value of \(\ell\), then the minimum value in Eq. (2) give us an upper bound for the unilateral diameter \(D^*\). The first case in which such a bound is not attained corresponds to N=430, where the unilateral diameter \(D^*\) is 22 and the upper bound given by Eq. (2) is 23.

4. The \((\Delta, D^*)\) and \((\Delta, N)^*\) problems for double-step digraphs with unilateral diameter

In this section we completely solve the \((\Delta, D^*)\) problem for double-step digraphs with unilateral diameter and give infinite families of such digraphs which solve the \((\Delta, N)^*\) problem. Let us begin with the former.

Figure 7. Some of the possible L-shaped forms for N=48. The numbers indicate the distance from 0 to each vertex. Each vertex 0 and its farthest vertices are in bold.

Figure 8. The minimum unilateral diameter \(D^*\) with respect to \(\ell\) for N=48 and N=49.

4.1. The \((\Delta, D^*)\) problem

In our context, the \((\Delta, D^*)\) problem consists of finding the double-step digraph G(N; a, b) with maximum number of vertices given a unilateral diameter \(D^*\), that is, to find the steps that maximize the number of vertices for such a unilateral diameter. To get a Moore-like bound (see Miller and Sirán [9]), notice that at distance \(k=1,2,\ldots,D^*\) from vertex 0 there are at most 2(k+1) vertices (k+1) of them going forward and the other k+1 going backwards). Then, this gives

\[N \le M(2, D^*) = 2(1 + 2 + \dots + D^* + 1) - 1 = (D^*)^2 + 3D^* + 1.\] (3)

Moreover, if the maximum is attained, we get an 'optimal' X-shaped tile which tessellates the plane, as shown in Fig. 9 (right) for the case N=11. In the following result we show that this Moore-like bound can be always attained.

Proposition 4.1. For each integer value \(k \ge 0\), the double-step digraph G(N; 1, b), with \(N = M(2, k) = k^2 + 3k + 1\) and b = k + 1 has unilateral diameter \(D^* = k\).

Table 1. The unilateral diameter D^∗ with respect to ` for N = 48 and N = 49 (in bold there are the values that satisfy <sup>1</sup> < ` ≤ d√ Ne)

Proof. This corresponds to one of the cases of Proposition 3.1. Indeed, it suffices to take ` = h = k + 1 and s = k.

In Table 3 there are the computer data of the minimum unilateral diameter for each number of vertices (5 ≤ N ≤ 106) with steps a = 1 and b = `. In bold, there are the cases corresponding to the (∆, D^∗ ) problem.

4.2. The (∆, N) ^∗ problem

In our context, the (∆, N) ^∗ problem consists of finding the minimum unilateral diameter D^∗ in double-step digraphs given a number of vertices N, that is, to find the steps that minimize the unilateral diameter for such a number of vertices. We begin with the following general upper bound for the unilateral diameter.

Proposition 4.2. Given any number of vertices N ≥ 5, there exists a double-step digraph with unilateral diameter D^∗ satisfying

\[D^* \le \left\lceil \sqrt{2(N+2)} \right\rceil - 2.\]

Proof. To prove the upper bound, we use again the constructions of Proposition 3.1. Then, suppose that, in the worst case, the division of N by `, where ` ≥ 2, gives a remainder s = ` − 2. Thus, N = `h + s with h = N−s ` = N+2 ` − 1 and this gives a unilateral diameter

\[D^* = \left\lfloor \frac{\ell + h + s - 1}{2} \right\rfloor = \left\lfloor \frac{N+2}{2\ell} + \ell \right\rfloor - 2.\]

Figure 9. The digraph G(11; 1, 4) (left), and its corresponding X-shaped tile (right).

Now, since we can choose the value of \(\ell\), we want to minimize the function \(\phi(\ell) = \frac{N+2}{2\ell} + \ell\), which is attained at \(\ell = \sqrt{(N+2)/2}\). Then, the claimed upper bound is obtained by considering that \(\ell\) must be an integer.

To solve the \((\Delta, N)^*\) problem for double-step digraphs with minimum unilateral diameter we consider the case \(s = \ell - 1\) of Proposition 3.1. Moreover, in this case, to keep track of the excluded vertices from the maximum M(2, k) (those corresponding to the white squares in Fig. 4), we define r as the subindex of the triangular number \(T_r = 1 + 2 + \cdots + r = {r+1 \choose 2}\).

Proposition 4.3. (a) If \(0 \le r < \frac{1}{2}(\sqrt{8k+9}-1)\), the double-step digraph G(N;a,b), with number of vertices \(N=k^2+3k+1-r(r+1)\) and steps a=1 and \(b=\ell=k-r+1\), has minimum unilateral diameter \(D^*=k\).

(b) If \(0 \le r < \sqrt{k+1}\), the double-step digraph G(N; a, b), with number of vertices \(N = k^2 + 2k - r^2\) and steps a = 1 and \(b = \ell = k - r + 1\), has minimum unilateral diameter \(D^* = k\).

Proof. (a) In Proposition 3.1, take \(\ell=k+1-r\), h=k+1+r, and \(s=\ell-1\). This corresponds to a double-step digraph with number of vertices \(N=\ell h+s=(k+1-r)(k+1+r)+k-r=k^2+3k+1-r(r+1)\) and unilateral diameter \(D^*=\lfloor (\ell+h-1)/2\rfloor=k\). Thus, if the number r(r+1) of excluded vertices from the maximum M(2,k) is at most 2k+1, the digraph has minimum unilateral diameter for this N. This comes from the fact that M(2,k)-M(2,k-1)=2k+2. Using the triangular numbers, the condition is \(2T_r \leq 2k+1\). As \(2T_r\) is an even number, we get

\[2T_r \le 2k \quad \Leftrightarrow \quad T_r \le k \quad \Leftrightarrow \quad T_r = \frac{r(r+1)}{2} < k+1.\]

So, \(r^2 + r - (2k + 2) < 0\) and, hence, \(r < \frac{1}{2}(-1 + \sqrt{8k + 9})\).

(b) Using the same proposition, take \(\ell = k+1-r\), h=k+r, and \(s=\ell-1\), which corresponds

Figure 10. The minimum unilateral diameter D^∗ with respect to the number of vertices N, for 5 ≤ N ≤ 106. (The largest points correspond to the (∆, D^∗ ) problem, and the thick lines to the upper bound given in Proposition 4.2.)

to a double-step digraph with order N = `h + s = (k + 1 − r)(k + r) + k − r = k <sup>2</sup> + 2k − r 2 and, as before, unilateral diameter D<sup>∗</sup> = b(` + h − 1)/2c = k. Now, for the digraph to have minimum unilateral diameter, the number of excluded squares from M(2, k) must satisfy

\[T_r + T_{r-1} + k + 1 = \frac{(r+1)r}{2} + \frac{r(r-1)}{2} + k + 1 = r^2 + k + 1 \le 2k + 1.\]

Then, \[r^2 \le k\] and, hence, \(r \le \sqrt{k}\) or \(r < \sqrt{k+1}\).

As said before, in Table 3 there are the computer data of the minimum unilateral diameter for each number of vertices (5 ≤ N ≤ 106) with steps a = 1 and b = `. The (∆, D^∗ ) problem, which are in bold, correspond to r = 0 in case (a). In grey, there are the cases corresponding to the (∆, N) ^∗ problem solved with Proposition 4.3. As shown in Fig. 10, the unilateral diameter D^∗ does not increase monotonically with the number of vertices N.

Note that if we fix r for any k large enough, we get an infinite family of digraphs with minimum unilateral diameter for each number of vertices. See some examples of the cases of Proposition 4.3 in Table 2.

Table 2. Some results of the (∆, D^∗ ) and (∆, N) ^∗ problems solved with Proposition 4.3

5. The mean unilateral distance for double-step digraphs

In the next result, we give the mean unilateral distance for the double-step digraphs of Proposition 3.1. There is an example of each kind of L-shaped form in Fig. 11.

Proposition 5.1. For ^{N =} `h+s, where <sup>1</sup> < ` ≤ d√ Ne and 0 ≤ s ≤ `−1, a double-step digraph G(N; a, b) with a = 1 and b = ` has mean unilateral distance d, where:

• (a) For s = 0:
  • (a1) If `, h are even: d = `h h h 2 2 + (` − 1) 3 `(2 − `) + `+h 2 2 − `+h 2 i.
  • (a2) If ` is even, and h is odd: d = 1 `h h h 2 2 + h 2 + (` − 1) 1 3 `(2 − `) + `+h 2 2 i.
  • (a3) If ` is odd, and h is even: d = 1 `h h h 2 2 + (` − 1) 1 3 `(2 − `) + `+h 2 2 i.
  • (a4) If `, h are odd: d = 1 `h h h 2 2 + 2 h 2 + 1 + (` − 1) 1 3 `(2 − `) + `+h 2 2 i.
• (b) For s = ` − 1:
  • (b1) If ` + h is even: d = `h+`−1 ` 1 3 (` − 1)(2 − `) + `+h 2 2 − `+h 2 .
  • (b2) If ` + h is odd: d = 1 `h+`−1 ` 1 3 (` − 1)(2 − `) + `+h 2 2 .

Table 3. Minimum unilateral diameter D^∗ for each number of vertices N, 5 ≤ N ≤ 106, with steps a = 1 and b = ` (the cases of the (∆, D<sup>∗</sup> ) problem are in bold, the cases with s = 0 are in white, with 1 ≤ s ≤ ` − 2 are in light grey, and with s = ` − 1 are in dark grey)

• (c) For 1 ≤ s ≤ ` − 2:
  • (c1) If `, h, s are even: d = 1 `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 2 + 1 3 (` − s − 1)(` − s)(2` + s − 1) + (` − s − 1) `+h+s 2 2 − `+h+s <sup>2 −</sup> (` ^{− s} + 2)(` <sup>− s</sup> + 1)i .
  • (c2) If `, h are even, and s is odd: d = 1 `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 2 + s+h 2 + 1 3 (` − s − 1)(` − s)(2` + s − 1) + (` − s − 1) `+h+s 2 2 − (` − s)(` − s + 1)i .
  • (c3) If `, s are even, and h is odd: d = `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 2 + 2 s+h 2 + 1 + 1 3 (` − s − 1)(` − s)(2` + s − 1) + (` − s − 1) `+h+s 2 2 − (` − s + 2)(` − s + 1)i.
  • (c4) If ` is odd, and h, s are even: d = 1 `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 ) 2 + 1 3 (` − s − 1)(` − s)(2` + s − 1) + (` − s − 1) `+h+s 2 2 − (` − s + 2)(` − s + 1)i.
  • (c5) If ` is even, and h, s are odd: d = 1 `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 2 + 3 (` − s − 1)(` − s)(2` + s − 1) + (` − s − 1) `+h+s 2 2 − `+h+s 2 − (` − s)(` − s + 1)i .
  • (c6) If `, s are odd, and h is even: d = 1 `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 2 + s+h 2 + 3 (` − s − 1)(` − s)(2` + s − 1) + (` − s − 1) `+h+s 2 2 − `+h+s 2 − (` − s)(` − s + 1)i .
  • (c7) If `, h are odd, and s is even: d = `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 2 + s+h 2 + 3 (` − s − 1)(` − s)(2` + s − 1) + (` − s − 1) `+h+s 2 2 − `+h+s 2 ) − (` − s + 2)(` − s + 1)i .
  • (c8) If `, h, s are odd: d = `h+s h (s + 1) 1 3 s(1 − s) + s+h 2 ) 2

Figure 11. The cases of Proposition 5.1 (the vertices with an asterisk are the farthest from 0).

\[+ \frac{1}{3}(\ell - s - 1)(\ell - s)(2\ell + s - 1) + (\ell - s - 1)\left(\left\lfloor\frac{\ell + h + s}{2}\right\rfloor^2 - (\ell - s)(\ell - s + 1)\right)\right].\]

Proof. We only prove case (c1) because the other proofs are very similar.

(c1) If \(\ell\), h and s even:

We divide the L-shaped form into two parts, the left one and the right one. In the left part, we have an L-shaped form with 'width' s+1 and 'height' h (with \(s\neq 0\)). In the right part, there is an L-shaped form with 'width' \(\ell-s-1\) and 'height' h (with s=0). See case (c1)

in Figure 11. Then, in the left part, the sum of the number of vertices times their distance is

\[2\left(2 \cdot 1 + 3 \cdot 2 + \dots + (s+1)s\right)\] \[+2\left((s+1)(s+1) + (s+1)(s+2) + \dots + (s+1)\left(\frac{s+h}{2} - 1\right)\right) + (s+1)\frac{s+h}{2}\] \[= 4\left(\binom{2}{2} + \binom{3}{2} + \dots + \binom{s+1}{2}\right)\] \[+2(s+1)\left[\left(1 + 2 + \dots + \frac{s+h}{2} - 1\right) - (1 + 2 + \dots + s)\right] + (s+1)\frac{s+h}{2}\] \[= 4\binom{s+2}{3} + (s+1)\left[\left(\frac{s+h}{2} - 1\right)\frac{s+h}{2} - s(s+1)\right] + (s+1)\frac{s+h}{2}\] \[= (s+1)\left(\frac{1}{3}s(1-s) + \left(\frac{s+h}{2}\right)^2\right).\]

For the right part, we have

\[\begin{split} &2[(s+1)\cdot 1 + (s+2)\cdot 2 + \dots + (\ell-1)(\ell-s-1)] \\ &+2(\ell-s-1)\left[(\ell-s+2) + \dots + \left(\frac{\ell+h+s}{2}-1\right)\right] \\ &= 2[(s-1)\cdot 1 + (s-1)\cdot 2 + \dots + (s-1)(\ell-s-1)] \\ &+2[2\cdot 1 + 3\cdot 2 + \dots + (\ell-s)(\ell-s-1)] \\ &+2(\ell-s-1)\left[1 + 2 + \dots + \left(\frac{\ell+h+s}{2}-1\right)\right] \\ &-2(\ell-s-1)\left(1 + 2 + \dots + \ell-s-1\right) \\ &= (s-1)(\ell-s-1)(\ell-s) + 4\left[\binom{2}{2} + \binom{3}{2} + \dots + \binom{\ell-s}{2}\right] \\ &+(\ell-s-1)\left(\frac{\ell+h+s}{2}-1\right)\frac{\ell+h+s}{2} - (\ell-s-1)(\ell-s+1)(\ell-s+2) \\ &= (s-1)(\ell-s-1)(\ell-s) + 4\binom{\ell-s+1}{3} \\ &+(\ell-s-1)\left(\frac{\ell+h+s}{2}-1\right)\frac{\ell+h+s}{2} - (\ell-s-1)(\ell-s+1)(\ell-s+2) \\ &= \frac{1}{3}(\ell-s-1)(\ell-s)(2\ell+s-1) \\ &+(\ell-s-1)\left(\left(\frac{\ell+h+s}{2}\right)^2 - \frac{\ell+h+s}{2} - (\ell-s+2)(\ell-s+1)\right). \end{split}\]

Finally, considering both parts, we obtain the mean unilateral distance dividing by the number of vertices N = `h + s.

Acknowledgement

This research was supported by the Ministry of Science and Innovation (Spain) and the European Regional Development Fund under project MTM2011-28800-C02-01-1 and by the Catalan Research Council under project 2009SGR1387.

References

• [1] F. Aguilo and M.A. Fiol, An efficient algorithm to find optimal double loop networks, ´ Discrete Math. 138 (1995), 15–29.
• [2] R. Beivide, E. Herrada, J.L. Balcazar, and A. Arruabarrena, Optimal distance networks of ´ low degree for parallel computers, IEEE Trans. Comput. 40 (1991), 1109–1124.
• [3] J.C. Bermond, G. Iliades, and C. Peyrat, An optimization problem in distributed loop computer networks, in Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985), Ann. New York Acad. Sci. 555 (1989), 45–55.
• [4] A. Brawer, and J. Shokley, On a problem of Frobenius, J. Reine Angew. Math. 211 (1962), 215–220.
• [5] P. Esque, F. Aguil ´ o, and M.A. Fiol, Double commutative-step digraphs with minimum diam- ´ eters, Discrete Math. 114 (1993), 147–157.
• [6] M.A. Fiol, J.L.A. Yebra, I. Alegre, and M. Valero, A discrete optimization problem in local networks and data alignment, IEEE Trans. Comput. C-36 (1987), 702–713.
• [7] J. Gomez, E.A. Canale, and X. Mu ´ noz, On the unilateral ˜ (∆, D^∗ )-problem, Networks 36(3) (2000), 164–171.
• [8] J. Gomez, E.A. Canale, and X. Mu ´ noz, Unilaterally connected large digraphs and generalized ˜ cycles, Networks 42(4) (2003), 181–188.
• [9] M. Miller and J. Siran, Moore graphs and beyond: A survey of the degree/diameter problem, ´ Electron. J. Combin. 20(2) (2013), DS14v2.
• [10] P. Morillo, M.A. Fiol, J. Fabrega, The diameter of directed graphs associated to plane tesse- ` lations, Ars Combin. 20A(4) (1985), 17–27.
• [11] J.L.A. Yebra, M.A. Fiol, P. Morillo, and I. Alegre, The diameter of undirected graphs associated to plane tesselations, Ars Combin. 20B(4) (1985), 159–171.