Diameter and Mean Distance of Bipartite Digraphs Related to Plane

Tessellations ^{∗}

F. Comellas^{†} Informatics Department Rutherford Appleton Laboratory Chilton, Didcot, England

P. Morillo M. A. Fiol Departament de Matemàtica Aplicada i Telemàtica Universitat Politècnica de Catalunya Barcelona, Spain

Abstract

It is possible to associate plane tessellations with certain digraphs over the set of vertices V = Z/nZ. This association enables a geometrical, and in general simpler, approach to their study. We use this relation for obtaining the maximum order, minimum diameter and minimum mean distance of a family of bipartite digraphs of degree two. The results found improve those known for similar families of digraphs with the same degree.

Ars Combinatoria, 29B, pp. 245–254 (1990).

1 Introduction

Graph Theory may facilitate the study of the topologies of interconnection networks in distributed systems. The association of a certain graph to a given topology means that parameters and properties of the graph such as diameter, degree, mean distance, existence of short paths between vertices, etc, may be directly related to characteristics in the network such as communication delay, throughput, mean transmission time, routing of messages, etc. One of the simplest topologies for an interconnection network is the ring structure in which each node is connected to another node forming a unidirectional loop. This topology has been widely used because of its simplicity, easy implementation and expandability. However, it has some inconveniences, namely: a poor reliability, and a large diameter and mean distance. One way of improving the performance of this topology is by the addition of links. In the simplest case one new link is added to each node. In this case the corresponding digraph has degree two. Several authors have worked on this problem looking for the best way of adding new links in order to obtain optimal digraphs. In general, arithmetical techniques are considered, but in several cases the use of a geometrical approach is very useful, see [1] [5] . The first reference to the use of plane tessellations in studying families of digraphs of degree two, may be found in the article of Wong and Coppersmith [6]. They considered the case in which vertices are labeled with integers modulo n, and vertex i is adjacent to vertices i+1 and i+s (modulo n). In their study, for a given n, they find values of s that minimize the diameter and the mean distance of the digraph. The general case, in which vertex i is adjacent to vertices i+a and i+b (modulo n), has been considered by Fiol, Yebra, Alegre and Valero [2] that visualize the problem geometrically, as follows: If the arc (i, i+a) is represented by a horizontal segment and the arc (i, i+b) by a vertical one, the distance between two points is obtained by adding the number of horizontal and vertical segments (see Figure 1).

∗\begin{matrix}c \\ ◯ \end{matrix}Ars Combinatoria 29B(1990), pp. 245–254.

†Permanent address: Departament de Matemàtica Aplicada i Telemàtica, Universitat Politècnica de Catalunya, ETSE Telecomunicació, Girona Salgado s/n, 08034 Barcelona, Spain

[figure: 0; a; 2a; 3a; 4a; b; a + b; 2a + b; 3a + b; 2b; a + 2b; 2a + 2b; 3b; a + 3b; 4b]

Figure 1: Planar pattern for a double fixed step digraph

In this geometrical context, the problem consists of finding a tile that has n unit squares and periodically tessellates the plane, and a and b such that the n unit squares of the tile are numbered from 0 to n−1 (see Figure 2 for such a realization with n = 9, a = 1, b = 7).

In this paper a further generalisation is considered . In the next Section we introduce a family of bipartite digraphs of degree two that may be associated with a plane tessellation. In Sections Three and Four we study three characterists of these digraphs: maximum order for a given diameter, minimum diameter

0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5

Figure 2: A double fixed step digraph with n=9, a=1 and b=7

for a given order and mean distance. The results obtained show that, for a given order, the minimum diameter and minimum mean distance of these digraphs are smaller than the corresponding values for comparable families of digraphs of degree two.

2 Bipartite digraphs

The digraphs considered in this paper have an even number of vertices n that belong to the set V = V_{0} ∪V_{1}, where V_{0} = {0, 2, .., n−2} and V_{1} = {1, 3, .., n−1}. Each vertex iϵV_{0} is adjacent to vertices i+a and i+b mod n, where a and b are different odd integers, and each vertex jϵV_{1} is adjacent to vertices j+c and j+d mod n for different odd integers c and d such that a+b+c+d = 0 (modulo n). See Figure 3.

From this definition it is clear that these digraphs are bipartite and we will denote them BD(n; a, b, c, d).

The digraphs are regular with degree 2 and are connected iff gcd(a + c, b + d, n) = 2.

The digraphs are not vertex-symmetric, but there exist automorphisms i → j+α for α even, i, j ∈ V_{0}, and k → l+β for β even, k, l ∈ V_{1}.

3 Diameter

The first optimisation problem to be considered consists of finding a, b, c, d such that, for a given order n, the digraph has minimum diameter. First let us consider the related optimisation problem of finding the maximum order of a

[figure: j; j + c; j + d; i; i + b; i + a; V_{1}; V_{0}]

Figure 3: Adjacencies in a BD(n; a, b, c, d)

BD(n;a,b,c,d) of given diameter k. An upper bound may be easily found [3]. There are 2j vertices at distance j from a given vertex. If we consider the case of an even vertex, since the digraphs are bipartite, the maximum order n_{k} of a digraph with diameter k, is twice the number of vertices in V_{1} if k is even, or twice the number of vertices in V_{0} if k is odd. That is:

a) k even. At distance j there are ∑_{j=1 odd}^{k−1} 2j vertices in V_{1}. Hence:

n_{k} = 2 ∑_{j=1 odd}^{k−1} 2j = k^{2}

b) k odd. There are 1 + ∑_{j=2 even}^{k−1} 2j vertices of V_{0} at distance j from the given even vertex. Therefore:

n_{k} = 2(1 + ∑_{j=2 even}^{k−1} 2j) = k^{2}+1

The same result may be obtained starting from an odd vertex.

Next it is shown that this upper bound may be reached if the diameter is odd, but is not if the diameter is even.

This study is based in the following observations:

a) Periodicity. Let consider the regular tessellation of the plane with squares. Each square is numbered according to the patterns in Figure 3. As a consequence, every square contains an integer from 0 to n-1 and the distribution repeats itself periodically. This is illustrated in the example of Figure 4 for the digraph BD(26;1,-1,5,-5).

b) Tessellation. Consider a tile with n squares, labeled 0 to n-1. By the periodicity property, this tile tessellates the plane. See Figure 4.

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 14 15 16 17 18 19 20 21 22 23 24 25 0 1 2 3 4 19 20 21 22 23 24 25 0 1 2 3 4 5 6 7 8 9 24 25 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 13 14 15 16 17 18 19 20 21 22 23 24 25 0 1 2 3 18 19 20 21 22 23 24 25 0 1 2 3 4 5 6 7 8 23 24 25 0 1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Figure 4: BD(26;1,-1,5,-5)

In this context, the optimisation problem of finding the maximum order of a digraph with diameter k, consists of finding and implementing tiles such that, starting from any node all the squares of the tile may be reached in less than k steps, and the tile has the maximum possible number of squares . The main difference with the same problem for the digraphs studied by Fiol et al. [2], is that in their case the digraphs are always vertex-transitive and the problem may be divided in two separate steps: finding an optimal tile and implementing it. In our case this is not possible and the implementation problem has to be solved simultaneously to the search for the optimal tile.

We have to distinguish between k even and k odd.

k odd. The following result gives the optimal tiles in this case.

Theorem 1. There exists a BD(k^{2} +1; a, b, c, d) with diameter k odd, if a = 1 = −b and c = k = −d.

Proof: That the bound, calculated above, is attained with the given values of a, b, c, d, may be seen geometrically, as shown in Figure 4. The integers between 0 and n−1 are ranged enumeratively in rows forming a tile that tessellates the plane and any of the vertices may be reached in at most k steps starting from an even (or odd) vertex. The same result may be obtained arithmetically.

The values that implement the tile are obtained solving the equations that give the distribution of zeros. See Figure 5:

k(a + c) + (a + d) = 0 mod n
\frac{k+1}{2}(a + c) + \frac{k−1}{2}(b + c) = 0 mod n
a + b + c + d = 0 mod n

This has one solution a = 1 = −b and c = k = −d.

0  0 0

Figure 5: Optimal tiles, tessellation and zero distribution for k odd

k even. In this case the optimal tile cannot be implemented, because there is no way of reaching, given the tessellation, all vertices in at most k steps, starting from any vertex. The optimal tile in this case may be found once again by using plane tessellations.

The maximum order for k even is given by the following theorem:

Theorem 2. The maximum order of a BD(n_{k}; a, b, c, d) with diameter k, even, is n_{k} = k^{2}+3 and that bound is attained for a = 1 = −b and c = k−1 = −d.

Proof: By case analysis, and from the different possible optimal tiles for k−1, odd, we have found that there is no way of adding more than two vertices without increasing the diameter to at least k+1. If we add only two vertices one possible optimal tile with diameter k is shown in Figure 6.

The actual values that implement the tile are obtained, as in the case of k odd, by solving the equations that give the distribution of zeros. See Figure 6:

Let us return to the initial problem of determining the minimum diameter of BD(n; a, b, c, d), for any value of n. The following two theorems cover the

0  0  0

Figure 6: Optimal tiles, tessellation and zero distribution for k even

values of n not considered so far.

Theorem 3. If (k−2)^{2} + 3 < n ≤ (k−1)^{2}, k odd, then the minimum diameter of BD(n;a,b,c,d) is k, and the bound is achieved with a = 1 = −b and c = k−2 = −d (mod n).

Proof: This corresponds to tiles that may be obtained from the optimal tile with diameter k−1 by adding two vertices each time to the left of the lower (incomplete) row as is shown in Figure 7.

Now, in the same way than for the optimal tiles, it is possible to find the values of a, b, c, d that enable the implementation from the corresponding distribution of zeros.

Theorem 4: If (k−1)^{2} ≤ n ≤ k^{2} + 1, k odd, then the minimum diameter of BD(n;a,b,c,d) is k and the bound is achieved with a = 1 = −b and c = k = −d (mod n).

Proof: In this case we start with the optimal tile with diameter k, odd, by deleting pairs of vertices first in right of the upper row and after in the left of the lower row. See Figure 8.

4 Mean distance

For any value of n, we may obtain closed equations for the minimum mean distance, and the values of a, b, c and d, that enable the construction of the digraph .

\overline{}^{k}  ^{k}  ^{k}  ^{k}^{k−1}  ^{k−1}  ^{k−1}  ^{k−1}^{0}

Figure 7: It is possible to obtain a tile for any n, (k − 2)^{2} + 3 < n ≤ (k − 1)^{2} (k odd) by adding pairs of vertices to the optimal tiles with diameter k − 1. The values in this figure denote the distance of the vertex from vertex 0

[figure: k−1; k−1; k−1; k−1; k; k; k; k; k−1; k−1; k−1; k; k; k; 0]

Figure 8: Tile for n such that (k−1)^{2} ≤ n ≤ k^{2} + 1, k odd. The values in this figure denote the distance of the vertex from vertex 0

The digraphs corresponding to the optimal cases are vertex-transitive, so we may easily find a closed formula for the mean distance. We have to distinguish between the cases of diameter even and diameter odd:

k even:

Theorem 5: The mean distance of BD((k−1)^{2} + 3; a, b, c, d) is:

k̄ ≥ \frac{2k^{3} − 6k^{2} + 13k − 6}{3k^{2} − 6k+9}

The bound is attained with a = 1 = −b, c = k−1 = −d.

Proof: The minimum mean distance is attained when all vertices are at the minimum possible distance from a given vertex. In this case, from geometrical considerations on the tessellation, and for a given diameter k, there are 2j vertices at distance j from vertex 0, for j between 1 and k−2, one vertex is at distance k and the remaining vertices are at distance k−1, see Figure 9. Therefore:

(n − 1)k̄ = ∑_{1}^{k−2} 2j^{2} + k + (n − ∑_{1}^{k−2} 2j − 2)(k − 1)

This yields the stated result.

k odd:

Theorem 6: The mean distance of BD(k^{2} + 1; a, b, c, d) is:

k̄ ≥ \frac{2k^{2} + 1}{3k}

The bound is attained with a = 1 = −b, c = k = −d.

Proof: In this case, as above and from geometrical considerations on the tessellation, for a given diameter k, there are 2j vertices at distance j from vertex 0, for j between 1 and k−2, k vertices are at distance k and the remaining vertices are at distance k−1, Figure 9. Therefore:

(n − 1)k̄ = ∑_{1}^{k−2} 2j^{2} + k^{2} + (n − ∑_{1}^{k−2} 2j − k − 1)(k − 1)

And the stated result is obtained.

It is not difficult to find equations for any other value of n, but it is rather cumbersome. The main difference with the optimal tiles is that, in some cases, the digraphs are not vertex-transitive and the distribution for both even and odd vertices must be counted on the tessellation.

The followings results cover all possible values of n.

Theorem 7: The minimum mean distance of a BD(n; a, b, c, d) for (k−2)^{2} + 3 < n ≤ (k−1)^{2} , k odd, is:

k̄ ≥ \frac{−k^{3} + 3k^{2} + 3nk − 2k − 3n − 6}{3(n − 1)}

k−2  k−2 k−1  k−1 k−2  k−1 k−2  k−2 k−1  k−1 k−3  k−3 k−3  k−3 k k−1 0  k−1  k−1 k  k k−1  k k−1  k−1 k  k k−2  k−2 k−2  k−2 0 k even  k odd

Figure 9: Distance distribution of vertices in optimal tiles with diameter k even and k odd.

The bound is achieved for every n by considering a BD(n; a, b, c, d) with a = 1 = −b c = k−2 = −d.

Proof: There are 2j vertices at distance j from any vertex for 1 ≤ j ≤ k−3. The remaining vertices are given as follows:

a) If starting from an even vertex, there are k−1 vertices at distance k−2, 1 at distance k−1, and the remaining vertices are equally distributed at distances k−1 and k.

b) If starting from an odd vertex, there are k−2 vertices at distance k−2 and the remanining vertices equally distributed at distances k−2 and k−1

Therefore the mean distance k̄ may be found from:

2(n − 1)k̄ =

∑_{1}^{k−3} 2j^{2} + (k−1)(k−2) + (k−1) + (n − ∑_{1}^{k−3} 2j − (k−1) − 2)(\frac{k−1}{2} + \frac{k}{2} ) +

∑_{1}^{k−3} 2j^{2} + (k−2)(k−2) + (n − ∑_{1}^{k−3} 2j − (k−2) − 1)(\frac{k−2}{2} + \frac{k−1}{2})

by straightforward calculations.

Theorem 8: The minimum mean distance of a BD(n; a, b, c, d) for (k−1)^{2} ≤ n < k^{2}−k , k odd, is:

k̄ ≥ \frac{−k^{3} + 3k^{2} + 3nk − 2k − 3n − 6}{3(n − 1)}

The bound is achieved with a = 1 = −b c = k = −d.

Proof: In this case there are 2j vertices at distance j from any vertex for 1 ≤ j ≤ k−3. The remaining vertices are given as follows:

a) If starting from an even vertex there are 2(k−2) vertices at distance k−2, k−2 at distance k−1, and the remaining vertices are equally distributed at distances k−1 and k.

b) If starting from an odd vertex there are k−1 vertices at distance k−2, k−2 at distance k−1, k−3 at distance k, and the remanining vertices equally distributed at distances k−2 and k−1.

Theorem 9: The minimum mean distance of a BD(n; a, b, c, d) for k^{2} −k ≤ n < k^{2} + 1 , k odd, is:

k̄ ≥ \frac{−k^{3} + 3k^{2} + 3nk − 2k − 3n}{3(n − 1)}

The bound is achieved with a = 1 = −b c = k = −d.

Proof: There are 2j vertices at distance j from any vertex for 1 ≤ j ≤ k−3. The remaining vertices are given as follows:

a) If starting from an even vertex there are, 2(k−2) vertices at distance k−2, 3\frac{k−5}{2} at distance k−1, \frac{k−1}{2} at k, and the remaining vertices are equally distributed at distances k−1 and k.

b) If starting from an odd vertex there are, k vertices at distance k−2, k+1 at distance k−1, k−1 at distance k, and the remanining vertices equally distributed at distances k−2 and k−1.

5 Conclusions

In this paper the use of plane tessellations facilitates the study of a family of bipartite digraphs of degree two. Although, until now, the use of plane tessellations has been restricted to vertex-symmetric graphs and digraphs, here it is shown how this geometric approach may be useful for the study of graphs that have certain less restrictive automorphism groups acting on their vertex set. The results show that the family of digraphs of degree two studied has smaller minimum diameter and mean distance than similar families presented in the literature. See Table 1.

On the other hand, as is easily seen from the tessellation, the optimal cases for each diameter contain an Hamiltonian cycle. This means that the corresponding network may be constructed from a ring with the same number of nodes, simply by adding one new link to each node.

Open questions related with this family are the existence of Hamiltonian cycles in the general case, the description of routing algorithms in these digraphs and the study of the reliability when a node or arc fails.

Opt. Loop [4] Fixed Step [2] Bip. Digraphs
N k  k̄ k  k̄ k  k̄
30 9  4.50 8  4.30 7  3.72
40 10  5.25 9  5.10 7  4.31
60 13  6.63 12  6.50 9  5.25
80 15  7.90 14  7.63 9  5.98
100 18  9.00 16  8.70 11  6.75
120 19  9.92 17  9.55 11  7.31

Table 1: Comparative values of the diameter and mean distance for different digraphs of degree two

Acknowledgements

This work was supported by the CICYT under grant PA86-0173. F.C. acknowledges a Fleming award of the Ministerio de Educación y Ciencia, Spain, and The British Council.

References

[1] Bermond J-C.; F. Comellas and D.F.Hsu; “Distributed Loop Computer Networks: A Survey”, submited IEEE Trans. Comp..

[2] Fiol, M A; J. L. A. Yebra; I. Alegre and M Valero; “A Discrete Optimization Problem in Local Networks and Data Alignment”,IEEE Trans. Comp. C-36, pp 702-713, 1987.

[3] Morillo, P.; M.A. Fiol and J. Fabrega. “The Diameter of Directed Graphs Associated to Plane Tessellations”. Ars Combinatoria 20-A pp 17-27, 1985.

[4] Raghavendra, C.S.; M. Gerla and A. Avizienis. “Reliable loop topologies for large local computer networks ”, IEEE Trans. Comp. C-34, pp 185-187, 1985.

[5] Raghavendra, C.S. and J.A. Silvester. “A Survey of Multi-Connected Loop Topologies for Local Computer Networks”, Computer Networks and ISDN Systems 11, pp 29-42, 1986.

[6] Wong, C.K. and D. Coppersmith. “A combinatorial problem related to multimodule memory organizations”. J. Assoc. for Comp. Mach. 21 pp 392-402 (1974).