Metric Problems in Triple Loop Graphs and Digraphs Associated to an Hexagonal Tessellation of the Plane

P. Morillo, F. Comellas and M.A. Fiol Department of Mathematics E.T.S.E. Telecomunicació Universitat Politècnica de Catalunya Barcelona, Spain

Tech.Report 05-0286; June, 1986

ABSTRACT. The use of plane tessellations by hexagons facilitates the study of a family of triple loop digraphs and a family of triple loop graphs and enables us to give the minimum diameter, mean distance and vulnerability results for every order.

1 Introduction.

Most problems arising in the study of networks can be formulated in terms of graphs. One of them, the construction of efficient and reliable networks with a limited number of links, leads to the search of graphs that, with a fixed degree, have minimal diameter for a given order or maximum order for a given diameter. It also leads to the study of their vulnerability i.e. to find how the diameter increases when one or more vertices (or arcs) are deleted.

It is possible to associate plane tessellations to certain graphs [1]. This association enables a geometrical, and in general simpler, approach to the above mentioned search.

In this paper we deal with the study of some graphs related to hexagonal tessellations of the plane: a family of directed regular graphs of degree three and a family of undirected regular graphs of degree six. For both families the maximum order corresponding to a given diameter is known [2], [3]. Plane tessellations are considered in order to obtain the minimum diameter, mean distance and vulnerability of the graphs.

2 Triple loop digraphs.

The triple loop digraphs considered in this paper are digraphs with set of vertices V = {0, 1, …, n − 1} in which every vertex i ∈ V is adjacent to the vertices i + a, i + b and i + c (modn) whith a, b and c = a + b different integers between 1 and n−1. We denote these digraphs as T LD(a, b, c). They may be associated to an hexagonal tessellation of the plane (Figure 1), are regular of degree 3 and are connected iff gcd(a, b, n) = 1. The maximum order of a T LD(a, b, c) of diameter k is n_{k} = (k +1)^{2} , and this bound is a chieved with a = 1 and b = k + 1, see [3].

The following theorem gives the minimum diameter of these digraphs:

Theorem 1. The minimum diameter of a T LD(a, b, c) with n vertices is k_{n} = ⌊(n − 1)^{\frac{1}{2}} ⌋. This diameter is obtained by considering a = 1 and b = k_{n} + 1. Theorem

Proof. Note that the integer k_{n} must satisfy:

n_{k−1} < n ≤ n_{k}

Figure 1:

That is

k_{n}^{2} < n ≤ (k_{n} + 1)^{2}

which is equivalent to

−1 + (n − 1)^{\frac{1}{2}} < k_{n} ≤ (n − 1)^{\frac{1}{2}}

and therefore

k_{n} = ⌊(n − 1)^{\frac{1}{2}} ⌋

Furthermore, with the choice of a = 1 and b = k_{n} + 1 the vertices at distance at most k_{n} are all the integers between 0 and k_{n}(k_{n} +2) ≥ n−1 hence the tile corresponding to n_{k} contains all the integers modulo n. Then, from this tile it is possible to obtain the tile corresponding to a digraph of order n by deleting elements of the upper SW-NE diagonal (Figure 2).

Figure 2:

Theorem 2. The mean distance of a T LD(a, b, c) of order n is

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

where k_{n} = ⌊(n − 1)^{\frac{1}{2}} ⌋. This bound is achieved for every n by considering a digraph whith a = 1 and b = k_{n} or k_{n} + 1.

Proof. Since the digraph is vertex-transitive, the mean distance may be expressed as:

k_{n} = \frac{1}{n − 1} ∑_{i=1}^{n−1} d(0, i)

From the tessellation it is easy to see that there are at most 2j + 1 vertices at distance j from vertex 0, 1 ≤ j ≤ k_{n} − 1, so that:

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

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

and therefore

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

To show that the bound is achieved we study two cases:

a) n ≤ k_{n}^{2} + k_{n} + 1. If we consider the triple loop digraph of n vertices with a = 1 and b = k_{n} , the vertices i such that i < k_{n}^{2}(= n_{k−1}) are at most at distance k_{n} − 1 from vertex 0, and there are exactly 2j + 1 vertices at distance j from this vertex (j ≤ k_{n} − 1). It remains to prove that the other vertices are at distance exactly k_{n} from vertex 0. A vertex i is adjacent to the vertices i+k_{n} , i+1, i+k_{n} +1, therefore the set of neighbours of the vertices i ≤ k_{n}^{2} contains all the vertices j such that j ≤ k_{n}^{2} + k_{n} so that the vertices j that verify k_{2} ≤ j ≤ k_{n}^{2} + k_{n} are at distance k_{n} .

b) n ≥ k_{n}^{2} + k_{n} − 1. In the triple loop digraph of n vertices a = 1 and b = k_{n} + 1, the vertices i such that i ≥ (k_{n} − 1)(k_{n} + 1) + k_{n} are at distance k_{n} from vertex 0. Therefore as n ≥ k_{n}^{2} + k_{n} − 1 the distribution of the vertices at distance j(j < k_{n}) from vertex 0 is the same as in the digraph with (k_{n} + 1)^{2} vertices with a = 1, b = k_{n} + 1 and there are exactly 2j + 1 vertices at distance j while the remaining vertices are at distance k_{n}.

Theorem 3. The diameter of the digraph obtained by deleting one vertex (or arc) in a T LD(a, b, c) with diameter k is at most k + 1.

Proof. Suppose that we delete a vertex on a path of lenght less than k betwen vertices i and j. Then the distance d(i, j) can increase only if there is no other disjoint path of lenght less or equal than k between them. If this is the case the path has only steps of type a, b or c. There is no loss of generality in supposing that the steps on the affected path are of type a and that the initial vertex is −c.

Then we construct another route to a vertex ma − c as follows: after one step of type c (or of type b) there always exist a path of lenght less or equal than k from this new vertex - the 0 vertex- to the final vertex that does not go throught the deleted one (or arc) -see Figure 3-.

3 Triple loop graphs.

In this case each vertex i, 0 ≤ i ≤ n − 1, is adjacent to the vertices i ± a, i ± b, i ± c (modn) where a,b and c = −(a + b) are diferent integers 0 < a, b < ⌊\frac{n}{2}⌋. We express these graphs as T LG(a, b, c). The graphs may be associated to an hexagonal tessellation of the plane (Figure 4), are regular of degree 6 and are connected iff gcd(a, b, n) = 1. The maximum order of a triple loop graph of diameter k is n_{k} = 1 + 3k + 3k^{2} . The bound is achieved with a = 1 and b = 1 + 3k, see[2].

The problem of minimizing the diameter has been solved for some values of n (Table 1). For other values the solution is obtained by exhaustive computer search that has been also used for obtaining the minimum mean distance.

We study now the effect of the deletion of a vertex (or a arc) on the diameter of these graphs.

Figure 3: Figure 4:

Order  Diameter a  b
n_{k} − k  k  1  3k
n_{k} − 2k  k  1 3k − 1
n_{k} − 3k  k  1 3k − 2
n_{k} − 4k  k  1 3k − 2
n_{k} − 5k  k  1 3k − 4
n_{k} − 1  k + 1  1 3k + 1
n_{k} − (k + 1)  k  1  3k
n_{k} − 2(k + 1)  k  1 3k − 1
n_{k} − 3(k + 1)  k  1 3k − 2
n_{k} − 4(k + 1)  k  1 3k − 3
n_{k} − k + 1  k + 1  1  3k

Table 1:

Theorem 4. The diameter of the graph obtained by deleting one vertex (or arc) in a T LG(a, b, c) with diameter k is at most k + 1.

Proof. The distance can increase only if there is a unique path of lenght less or equal than k between the vertices i and j and the vertex deleted (or arc) is on the path, that is, if the path has only steps of type a, b or c. As in the proof of theorem 3, there is no loss of generality if we suppose that the deleted vertex v belongs to a path that has only steps of type a. Then, we can replace the subpath v − a, v, v + a by v − a, v − a − b, v − b, v + a. Similarly we can replace the edge v, v + a by the subpath v, v − c, v + a. In any case the distance increases by at most 1.

References

[1] Wong, C.K., Coppersmith, D. A combinatorial problem related to multimodule memory organizations. J. Assoc. Comput. Mach., 21, pp. 392–402 (1974)

[2] Yebra, J.L.A., Fiol, M.A., Morillo, P., Alegre, I. The diameter of undirected graphs associated to plane tessellations. Ars Combinatoria, 20B, pp. 159–172 (1985)

[3] Morillo, P., Fiol, M.A., Fabrega, J. The diameter of directed graphs associated to plane tessellations. Ars Combinatoria, 20 A, pp. 17–29 (1985).