Ville Junnila
email: viljun@utu.fi

Adaptive Identification of Sets of Vertices in Graphs

Keywords: Identifying codes, Adaptive identification, Fault-detection, Sensor networks

. The motivation for adaptive identification comes from applications such as sensor networks and fault detection in multiprocessor systems.

We present an optimal adaptive algorithm for identifying vertices in cycles. We also give efficient adaptive algorithms for identifying sets of vertices in different graphs such as cycles, king lattices and square lattices. Adaptive identification is also considered in Hamming spaces, which is one of the most widely studied graphs in the field of identifying codes.

Introduction

Let G = (V, E) be a simple connected undirected graph with V as the set of vertices and E as the set of edges. Assume that the set V of vertices of G is finite. Then the set E of edges of G is also finite. A non-empty subset of V is called a code, and its elements are called codewords. The distance d(x, y) is the number of edges in any shortest path between the vertices x and y. Let r be a positive integer. We say that x r-covers y if d(x, y) ≤ r. Define then the r-ball B r (x) of radius r centered at x ∈ V by B r (x) = {y ∈ V | d(x, y) ≤ r}.

If all the r-balls in G have the same cardinality, then the cardinality of an r-ball is denoted by V r (G). For X ⊆ V , we denote B r (X) = x∈X B r (x).

Let C ⊆ V be a code and X be subset of V . An I-set of the set X with respect to the code C is

I r (C; X) = I r (X) = B r (X) ∩ C.
A code C is called an r-covering (or an r-covering code), if the set I r (C, x) is non-empty for all x ∈ V . In other words, each vertex in G is r-covered by at least one codeword. The minimum cardinality of an rcovering of G is denoted by γ r (G). A code C is called an r-packing, if the number of vertices in I r (C, x) is at most one for all x ∈ V . In other words, the r-balls centered at the vertices of C are all pairwise disjoint. The maximum cardinality of an r-packing of G is denoted by c r (G). If a code C is both an r-covering and an r-packing of G, then C is called an r-perfect code. If there exists an (r, ≤ )-identifying code for a graph G = (V, E), then G is said to be (r, ≤ )identifiable.

The original motivation for identification comes from fault detection in multiprocessor systems [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF]. A multiprocessor system can be modeled as a graph, where vertices are seen as processor and edges as links between processors. A set of processors C ⊆ V corresponding to an identifying code is chosen. Then each processor in C sends an alarm signal, if there exists a faulty processor in its neighborhood. Now the set of alarming processors corresponds to an I-set I(X) of the identifying code, where X is the set of faulty processors. Hence, the set of faulty processors X can be located since each I-set is unique. Identifying codes can also be applied, for example, to sensor networks, where they are used in design of location and detection systems [START_REF] Ray | Robust location detection with sensor networks[END_REF]. The most studied underlying graphs for identification are, e.g., square and king lattices, Hamming spaces and cycles [START_REF] Lobstein | Watching systems, identifying, locating-dominating and discrminating codes in graphs[END_REF].

Assume that a given graph G may contain faulty vertices and that we can ask whether there is a faulty vertex (or faulty vertices) in B r (x) for all x ∈ V . The query Q r : V -→ {0, 1} is equal to 1 for x ∈ V , if there is a faulty vertex in B r (x), else Q r (x) is equal to 0. We also say that a vertex y ∈ V is r-covered by a query Q r (x) (x ∈ V ), if y belongs to the r-ball B r (x). Now the problem is to locate the faulty vertices using the queries Q r (x). The definition of identifying codes guarantees that if C ⊆ V is an (r, ≤ )-identifying code in G, then by asking simultaneously all the queries Q r (c) for c ∈ C we can locate in one step all the faulty vertices in G (assuming that there are at most faulty vertices in G).

The definition of identifying codes is based on the fact that all the queries have to be asked simultaneously. However, adaptive identification, which has been recently introduced in [START_REF] Ben-Haim | Adaptive identification in graphs[END_REF], is based on the idea that the queries can be asked one after the other, i.e. that a new query may depend on the answers given by the previous queries. In what follows, we call the identifying codes in Definition 1.1 as regular to distinguish them from the adaptive ones.

Let be the maximum number of faulty vertices in a graph G. The minimum cardinality of an (r, ≤ )identifying code in G is then denoted by i (r,≤ ) (G). In adaptive identification, the corresponding value is the minimum number of queries required in the worst case to identify the (at most ) faulty vertices and it is denoted by a (r,≤ ) (G). We also say that an algorithm (or a series of queries) A is adaptive (r, ≤ )-identifying, if it can identify the at most faulty vertices in G using only the queries Q r (x) (x ∈ V ).

In Ben-Haim et al. [START_REF] Ben-Haim | Adaptive identification in graphs[END_REF], [START_REF] Ben-Haim | Adaptive identification in graphs[END_REF] and [START_REF] Ben-Haim | Adaptive identification in tori in the king lattice[END_REF], adaptive (r, ≤ 1)-identification is considered in torii of square and king lattices. They suggest that further study would be needed in these torii when > 1. This motivated the study in Sections 2.2 and 2.4. Adaptive (r, ≤ )-identification in cycles and Hamming spaces are studied in Sections 2.1 and 2.3, respectively.

In adaptive (r, ≤ )-identification (and in regular (r, ≤ )-identification), it is common that we encounter problems with large . Namely, the considered graph is no longer (r, ≤ )-identifiable with large enough . For example, square and king lattices are not (r, ≤ )-identifiable when r > 1 and ≥ 3. Therefore, we introduce a slightly modified version of adaptive (r, ≤ )-identification in Section 3 to enable the handling of larger , for example, in king lattices.

Adaptive identification

The following theorem is a generalized version of Theorem 1 in [START_REF] Ben-Haim | Adaptive identification in graphs[END_REF][START_REF] Ben-Haim | Adaptive identification in graphs[END_REF].

Theorem 2.1 Let r and be positive integers. Assume G is an (r, ≤ )-identifiable graph such that each r-ball in G has the same cardinality. Then we have

a (r,≤ ) (G) ≥ c r (G) -1 + log 2 i=0 K i , where K = |G| -(c r (G) -1)V r (G).
Proof: Let G = (V, E) be an (r, ≤ )-identifiable graph such that each r-ball in G has the same cardinality. Consider then an algorithm A that is adaptive (r, ≤ )-identifying. It is clearly possible that the values given by the first c r (G) -1 queries of A are all equal to 0, i.e. that there are no faulty vertices in the r-balls of the first c r (G) -1 queries.

After the first c r (G) -1 queries there are still at least |G| -(c r (G) -1)V r (G) vertices that are not r-covered by any of the previously asked queries. Furthermore, we know that among these uncovered vertices there exist from 0 to faulty vertices. Therefore, the number of different possibilities for these faulty vertices to be among these uncovered vertices is i=0 K i , where K = |G| -(c r (G) -1)V r (G). Hence, we need at least log 2 ( i=0 K i ) queries to locate these faulty vertices or to conclude that there are none. Thus, the following lower bound follows:

a (r,≤ ) (G) ≥ c r (G) -1 + log 2 i=0 K i . 2 Notice that |G|-(c r (G)-1)V r (G) ≥ V r (G) since the value c r (G)
is the maximum number of vertices in an r-packing of G. Thus, the slightly weaker lower bound of Theorem 1 in [START_REF] Ben-Haim | Adaptive identification in graphs[END_REF][START_REF] Ben-Haim | Adaptive identification in graphs[END_REF] immediately follows from the previous result:

a (r,≤1) (G) ≥ c r (G) -1 + log 2 (V r (G) + 1) .

Adaptive identification in cycles

Let G be a cycle of length n, i.e. a cycle with n vertices. Regular identification in cycles have been studied, for example, in [START_REF] Bertrand | Identifying and locating-dominating codes on chains and cycles[END_REF], [START_REF] Gravier | Identifying codes of cycles[END_REF] and [START_REF] Roberts | Locating sensors in paths and cycles: The case of 2-identifying codes[END_REF]. The following theorem provides the accurate value for the number of queries a (r,≤1) (G) needed in the adaptive (r, ≤ 1)-identification of G, when n > 2r + 1. Notice also that if n ≤ 2r + 1, then the cycle G is not (r, ≤ 1)-identifiable.

Theorem 2.2 Let G be a cycle of length n. If n = 2r + 1 + k with 1 ≤ k ≤ 2r, then we have

a (r,≤1) (G) = 2r + 1 k + log 2 2r + 1 -k 2r + 1 k -1 . ( 1
)
If n ≥ 2(2r + 1), then we have

a (r,≤1) (G) = n 2r + 1 -1 + log 2 n - n 2r + 1 -1 (2r + 1) + 1 . (2)
Proof: Let G = (V, E) be a cycle of length n and V = {x 1 , x 2 , . . . , x n }. Consider first the result (1) for the cycles of length n = 2r + 1 + k with 1 ≤ k ≤ 2r. Notice that now each query outputting 1 tell us that one of the vertices covered by the query is faulty and also that none of the k uncovered vertices is faulty. Let us begin by showing a lower bound on a (r,≤1) (G) when n = 2r + 1 + k with 1 ≤ k ≤ 2r. We can assume that the first query asked outputs value 1. Therefore, the faulty vertex is one of the 2r + 1 vertices covered by the first query. We can assume that the next (2r+1)/k -1 queries also output value 1. By the considerations in the first paragraph above, there still exists at least 2r + 1 -k( (2r + 1)/k -1) vertices such that exactly one of them is faulty. Hence, we still need at least log 2 (2r + 1 -k( (2r + 1)/k -1)) queries to locate the faulty vertex. Thus, at least (2r + 1)/k + log 2 (2r + 1 -k( (2r + 1)/k -1)) queries is needed to identify the faulty vertex. Now the following algorithm is adaptive (r, ≤ 1)-identifying:

1. Begin by asking the query Q r (x r+1 ). If Q r (x r+1 ) = 0, then there does not exist any faulty vertex in B r (x r+1 ). Hence, the possible faulty vertex belongs to the remaining k vertices, which are consecutive ones in a cycle. Therefore, since k ≤ 2(2r + 1) + 1, we obtain using dichotomic (or binary) search (as in the step 3) that at most log 2 (k + 1) queries are needed to locate the faulty vertex among the remaining k vertices or to conclude there is none. It can be easily verified that in this case we use at most

(2r + 1)/k + log 2 (2r + 1 -k( (2r + 1)/k -1)) queries. 2. Assume that Q r (x r+1 ) = 1. Now for i = 1, 2, . . . , (2r + 1)/k -1 ask the query Q r (x r+1+ik ).
If the query Q r (x r+1+jk ) = 0 for some j, then the faulty vertex belongs to the set {x (j-1)k+1 , x (j-1)k+2 , . . . , x jk }, which consists of k consecutive vertices. Now the faulty vertex can be located in this set as in the step 3. Again it is easy to verify that also in this case we need at most (2r + 1)/k + log 2 (2r + 1 -k( (2r + 1)/k -1)) queries.

3. Assume now that all the (2r + 1)/k queries asked in the previous steps outputted the value 1.

Then the faulty vertex is one of the remaining 2r + 1 -k( (2r + 1)/k -1) vertices in the set

{x k( (2r+1)/k -1)+1 , x k( (2r+1)/k -1)+2 , . . . , x 2r+1 }.
Therefore, the faulty vertex can now be located by dichotomic search using at most log 2 (2r + 1k( (2r + 1)/k -1) queries. By the considerations in the first paragraph, the dichotomic search can now, indeed, be used since 2r + 1 -k( (2r + 1)/k -1) < 2k and there are k (2r + 1)/k consecutive vertices that are known to be not faulty (the set of uncovered vertices can now always be divided into two roughly equal halves).

Thus, we need at most (2r + 1)/k + log 2 (2r + 1 -k( (2r + 1)/k -1)) queries to locate the faulty vertex or to conclude there is none. In conclusion, the first result (1) of the claim holds. Consider then the result (2) for the cycles with length n ≥ 2(2r + 1). Denote first n = q 1 (2r + 1) + q 0 , where 0 ≤ q 0 < 2r + 1. Then consider the upper bound on a (r,≤1) (G). The following algorithm is adaptive (r, ≤ 1)-identifying:

1. For i = 1, . . . , q 1 -1 ask the query Q r (x i(2r+1)-r ). If Q r (x j(2r+1)-r ) = 1 for some 1 ≤ j ≤ q 1 -1,
then there exists a faulty vertex in B r (x j(2r+1)-r ). The vertices in the ball are clearly consecutive and, therefore, we can locate the faulty vertex by dichotomic (or binary) search as in step 2. Thus, the number of queries needed in this case is bounded above by the value given in the equation (2).

2. Assume then that all the vertices r-covered by the queries in step 1 are not faulty. Now there are still 2r + 1 + q 0 vertices that are not r-covered by any of the queries from step 1. Since the number of uncovered vertices is 2r + 1 + q 0 < 2(2r + 1), the possible faulty vertex can be located by dichotomic search. Hence, we need at most log 2 (2r + 1 + q 0 + 1) queries in this step.

Thus, we have a (r,≤1) (G) ≤ q 1 -1 + log 2 (2r + 1 + q 0 + 1) . By Theorem 2.1, we have a (r,≤1) (G) ≥ q 1 -1 + log 2 (2r + 1 + q 0 + 1) . Hence, the claim (2) immediately follows from the upper and lower bounds.

2

Consider then adaptive (r, ≤ 2)-identification in a cycle G of length n. By Theorem 2.1, we have

a (r,≤2) (G) ≥ n 2r + 1 -1 + log 2 2 i=0 K i , (3)
where K = n -( n/(2r + 1) -1) (2r + 1). The following theorem provides an upper bound on a (r,≤2) (G).

Theorem 2.3 Let G be a cycle of length n. If n ≥ 3(2r + 1), then we have

a (r,≤2) (G) ≤ n 2r + 1 + 1 + 2 log 2 (2r + 1) . (4)
Proof: Let G = (V, E) be a cycle of length n and V = {x 1 , x 2 , . . . , x n }. Denote also n = q 1 (2r+1)+q 0 , where 0 ≤ q 0 < 2r + 1. The following algorithm is adaptive (r, ≤ 2)-identifying:

1. For i = 1, . . . , q 1 , we first ask the queries Q r (x i(2r+1)-r ). If two of these queries give value 1, then we proceed as in step 3. Assuming this is not the case, we need to ask one additional (carefully chosen) query. If the first query Q r (x r+1 ) = 1, then the additional query is

Q r (x n-r ), else it is Q r (x (q1+1)(2r+1)-r )
, where the index of x is subtracted by n if it is larger than n. Notice that each vertex in G has now been r-covered by a query and that if two queries output value 1, then there exist two faulty vertices in G (one in each query giving value 1).

2. If all the queries in step 1 output value 0, then there clearly exist no faulty vertices in G.

3. If two of the queries in step 1 give value 1, then there are exactly two faulty vertices in G. Namely, one faulty vertex in each r-ball corresponding to the queries outputting 1. Denote these r-balls containing a faulty vertex by B 1 and B 2 . Note that the vertices in B 1 and B 2 are consecutive ones. Hence, the faulty vertex in B 1 (or B 2 ) can be located by dichotomic search and, in particular, using queries that do not r-cover vertices from B 2 (or B 1 ). (Here we use the assumption that n ≥ 3(2r + 1).) Therefore, the faulty vertices can be located by dichotomic search using at most 2 log 2 (2r + 1) queries.

4. If there is exactly one query giving value 1, then we know that this query is r-covering 1 or 2 faulty vertices. Denote the considered r-ball by B = {y 1 , y 2 , . . . , y 2r+1 } and assume that the two vertices adjacent to y 1 are y 0 and y 2 . The faulty vertices in B can then be located as follows:

(i) First the r-ball B is divided into two halves B 1 = {y 1 , . . . , y (2r+1)/2 } and B 2 = {y (2r+1)/2 +1 , . . . , y 2r+1 }. Then we find out whether there is a faulty vertex in B 1 or B 2 using the queries Q r (y 0 ) and Q r (y 2r+1 ).

(ii) If the halves B 1 and B 2 both contain a faulty vertex, then the faulty vertices from B 1 and B 2 can be separately located by dichotomic search. Otherwise, we know that only either B 1 or B 2 contain faulty vertices. For simplicity, assume that B 1 contains faulty vertices. Then we proceed as in step (i), but we replace the set B by B 1 .

Thus, in step 4 we locate the faulty vertices using at most 2 log 2 (2r + 1) queries.

In conclusion, the algorithm locates the faulty vertices using at most q 1 + 1 + 2 log 2 (2r + 1) queries. Thus, the claim follows. 2

Notice that the difference between the lower bound (3) and the upper bound (4) is at most 4 queries for any r and n. Indeed, this can be concluded by estimating the term with logarithm in the lower bound when the term with logarithm in the upper bound gives a fixed value. Hence, we conclude that the upper and lower bounds differ only by a constant (for any radius r).

Let G = (V, E) be a cycle of length n with V = {x 1 , x 2 , . . . , x n }. Since B r ({x 1 , x 3 }) = B r ({x 1 , x 2 , x 3 }) for any (positive) r, the cycle G is not (r, ≤ )-identifiable when ≥ 3.

Adaptive identification in torii of king lattice

Let p and q be positive integers. The graph T k p,q = (V, E) is a p × q torus in the king lattice, if the vertex set is

V = {(i, j) | 0 ≤ i ≤ p -1, 0 ≤ j ≤ q -1}
and the edge set is

E = {((i, j), (i, j + 1)), ((i, j), (i + 1, j)) | 0 ≤ i ≤ p -1, 0 ≤ j ≤ q -1} ∪ {((i, j), (i + 1, j + 1)), ((i, j), (i + 1, j -1)) | 0 ≤ i ≤ p -1, 0 ≤ j ≤ q -1},
where the first coordinate is calculated modulo p and the second coordinate is calculated modulo q (see Figure 1). Consider then an r-ball in T k p,q . The r-ball B r ((x, y)), which is shortened as B r (x, y), can be seen as a (2r + 1) × (2r + 1) square in the king lattice since

B r (x, y) = {(i, j) | |x -i| ≤ r, |y -j| ≤ r}.
Now it is easy to see that there exists an r-perfect code C ⊆ T k p,q if and only if both p and q are dividable by 2r + 1.

Regular (r, ≤ )-identification in king lattice (or grid) have been studied, for example, in [START_REF] Charon | The minimum density of an identifying code in the king lattice[END_REF] and [START_REF] Honkala | Codes for identification in the king lattice[END_REF]. Consider then adaptive (r, ≤ )-identification in T k p,q . If ≥ 3, then it can be easily seen that T k p,q is not (r, ≤ )-identifiable for any r. The case with = 1 is considered in [START_REF] Ben-Haim | Adaptive identification in graphs[END_REF][START_REF] Ben-Haim | Adaptive identification in tori in the king lattice[END_REF]. Thus, we concentrate here on the case with = 2. By Theorem 2.1, we have

a (r,≤2) (T k p,q ) ≥ pq (2r + 1) 2 -1 + log 2 2 i=0 (2r + 1) 2 i , (5)
since c r (T k p,q ) = pq/(2r + 1) 2 . The following theorem provides an upper bound for a (r,≤2) (T k p,q ). Theorem 2.4 Let p and q be positive integers dividable by 2r + 1. If p ≥ 3(2r + 1) and q ≥ 3(2r + 1), then we have

a (r,≤2) (T k p,q ) ≤ pq (2r + 1) 2 + 4 log 2 (2r + 1) . (6)
Proof: Assume p and q are positive integers dividable by 2r + 1. Let T k p,q be a torus in the king lattice with pq vertices. Now there exists an r-perfect covering C of T k p,q . The following algorithm is adaptive (r, ≤ 2)-identifying:

1. For every c ∈ C ask the query Q r (c).

2. If all the queries output value 0, then there clearly exist no faulty vertices in T k p,q .

3. If two queries output value 1, then there are two queries each r-covering exactly one faulty vertex.

The faulty vertex r-covered by a query can now be found as follows: we first locate by dichotomic search the column containing a faulty vertex and then from this column we identify the faulty vertex again using dichotomic search. (Notice that suitable queries used in dichotomic searches can be found even if the r-balls of the two queries are next to each other. Here we actually use the assumption that p ≥ 3(2r + 1) and q ≥ 3(2r + 1).) In conclusion, we need at most 4 log 2 (2r + 1) queries in this step.

4.

If there is exactly one query outputting value 1, then this query is r-covering 1 or 2 faulty vertices.

Using similar ideas as in the proof of Theorem 2.3, we can locate the columns (or a column) containing faulty vertices using at most 2 log 2 (2r + 1) queries (consider columns in the king lattice as the vertices in cycles) and then from these columns (or a column) identify the faulty vertices using at most 2 log 2 (2r + 1) queries. Thus, we need at most 4 log 2 (2r + 1) queries in this step.

In conclusion, the previous algorithm identifies the faulty vertices using at most pq/(2r+1) 2 +4 log 2 (2r+ 1) queries. 2

Using similar arguments as in the case of cycles, we conclude that the difference between the lower bound ( 5) and the upper bound ( 6) is at most 5 queries for any r.

Adaptive identification in Hamming spaces

In this subsection, we consider adaptive (1, ≤ )-identification in binary Hamming spaces. Let n be a positive integer. The binary Hamming space F n is the n-fold Cartesian product of the binary field F = {0, 1}. The Hamming distance d(x, y) between words x, y ∈ F n is the number of coordinate places in which they differ. The following simple lemma, which is needed in the sequel, can be easily proven.

Lemma 2.5 Let x, y ∈ F n . Then

|B 1 (x) ∩ B 1 (y)| =    n + 1 if x = y, 2 if 1 ≤ d(x, y) ≤ 2, 0 otherwise.
We begin by considering adaptive (1, ≤ 1)-identification in Hamming spaces. The following lemma is needed in the proof of Theorem 2.7, which provides a lower bound for a (1,≤1) (F n ). Lemma 2.6 Let X be a non-empty subset of F n . Assume that there is 0 or 1 faulty words in X. Then an adaptive (1, ≤ 1)-identifying algorithm needs at least |X| 2 queries, which are centered at a word in F n , to locate the faulty word in X or to conclude that there is none.

Proof: Let X be a non-empty subset of F n and let A be an algorithm that identifies the faulty word in X using queries from F n . Define then k as the maximum number of words in X that are 1-covered by a 1-ball of F n , i.e. k = max x∈F n |B 1 (x) ∩ X|. Now we have two approaches for the lower bound on the number of queries used in A:

(1) By the previous definition, a query Q 1 (x) with x ∈ F n can 1-cover at most k words of X. Assume that the first |X|/k -1 queries of A output value 0. Now there still exist at least k words that are not 1-covered by any of the previous queries, and we need at least log 2 (k + 1) queries to locate the faulty word among these uncovered words or to conclude that there is none. Thus, the number of queries used in A is at least |X|/k -1 + log 2 (k + 1) . If k = 1, then the claim clearly follows. Otherwise, we need at least |X|/k queries in the algorithm A.

(2) On the other hand, we know by Lemma 2.5 that the number of words in the intersection of two different 1-balls of F n is at most 2. Let then x ∈ F n be a word such that the number of words in B 1 (x) ∩ X is equal to k. Assume that there exists a faulty word in B 1 (x) ∩ X. Using similar arguments as in the first lower bound from (1), we obtain that the number of queries used in

A is at least k/2 -1 + log 2 2 if 2 | k, k/2 -1 + log 2 3 if 2 k.
Therefore, the number of queries needed is at least k/2.

By the considerations above, the number of queries needed in A is at least max{|X|/k, k/2}. Therefore, by straightforward analysis, it can be concluded that (with any choice of k) the number of queries needed is at least |X| 2 .

2

The following theorem provides a lower bound for a (1,≤1) (F n ).

Theorem 2.7 We have

a (1,≤1) (F n ) ≥ c 1 (F n ) + n + 1 8 .
Proof: Let algorithm A be an adaptive (1, ≤ 1)-identifying code (in F n ). (Notice that the size of a ball of radius 1 in F n is equal to n + 1.) Assume then that the first c 1 (F n ) -(n + 1)/8 queries of A output value 0. (By simple analysis, it can be shown that the number of queries c 1 (F n ) -(n + 1)/8 is chosen in such a way that it gives the best possible lower bound using this approach.) Then the number of words that are not 1-covered by the previous queries is at least (n + 1)/8 (n + 1). Therefore, by Lemma 2.6, the number of queries used in A is at least

c 1 (F n ) - n + 1 8 + (n + 1)/8 (n + 1) 2 ≥ c 1 (F n ) + n + 1 4 - n + 1 8 ≥ c 1 (F n ) + n + 1 8 ,
where the second inequality is obtained, for example, by considering two cases depending on whether n + 1 is dividable by 4 or not. 2

The following theorem provides an upper bound for a (1,≤1) (F n ).

Theorem 2.8 We have

a (1,≤1) (F n ) ≤ γ 1 (F n ) + n + 1 2 .
Proof:

Let C = {x 1 , x 2 , . . . , x |C| } be a 1-covering code of F n attaining γ 1 (F n ).
Denote then by e i the word in F n that has value 1 in the ith coordinate place and value 0 in all other places. Now the following algorithm is adaptive (1, ≤ 1)-identifying:

1. For i = 1, . . . , |C| -1 ask the query Q 1 (x i ). If Q 1 (x i ) = 1
for any i = 1, . . . , |C| -1, then the faulty word in B 1 (x i ) can be located as in the following step 2.

2. Assume then that all the previous queries output value 0, meaning that none of these queries do not 1-cover any faulty word. Now we can assume without loss of generality that x |C| = 0. For i = 1, . . . , n/2 -1 ask the query Q 1 (e 2i-1 +e 2i ). If now for any i we have Q 1 (e 2i-1 +e 2i ) = 1, then the faulty word can be located using one more suitably chosen query. Hence, assume that none of the previous queries 1-cover any faulty word. Now it can be easily seen that we only need two more queries to locate the faulty word in the remaining words or to conclude that there are none.

In conclusion, the previous algorithm uses at most

γ 1 (F n ) + n/2 + 1 = γ 1 (F n ) + (n + 1)/2 queries. 2
Let then F n be a Hamming space with integers n = 2 s -1 and s ≥ 3. By [START_REF] Cohen | Covering codes[END_REF], we know that there now exists a 1-perfect covering of F n . Hence, we have c 1 (F n ) = γ 1 (F n ) = 2 n /(n + 1). Therefore, for the previous lengths, Theorems 2.7 and 2.8 can be written as follows:

c 1 (F n ) + n + 1 8 ≤ a (1,≤1) (F n ) ≤ c 1 (F n ) + n + 1 2 .
As above, assume that n = 2 s -1 and s ≥ 3. Consider then adaptive (1, ≤ )-identification in F n with > 1. Theorem 2.7 naturally provides a lower bound also for a (1,≤ ) (F n ). The following theorem gives us then an upper bound on a (1,≤ ) (F n ). Theorem 2.9 Let n and s be integers such that n = 2 s -1 and s ≥ 3. If now < n/6 + 1, then we have

a (1,≤ ) ≤ c 1 (F n ) + • n + 3 2 . Proof: Let C be a 1-perfect code of F n with n = 2 s -1 and s ≥ 3. The number of words in C is equal to γ 1 (F n ) = c 1 (F n ). Denote then n = 2m + 1, where m = 2 s-1 -1. Using c 1 (F n
) queries, we can now locate the 1-balls centered at the words of C which contain faulty words. Assume then that the 1-balls B 1 (x 1 ), B 1 (x 2 ), . . . , B 1 (x k ) with 1 ≤ k ≤ are the ones containing faulty words. Denote the set consisting of these 1-balls by S.

Consider then locating the faulty words inside B 1 (x 1 ). We can assume without loss of generality that x 1 = 0. We would now like to 1-cover B 1 (0) using m words of weight two and 1 word of weight one (similarly to the proof of Theorem 2.8). However, here we cannot use such words of weight one and two which 1-cover words from other 1-balls containing faulty words. The choice of m words of weight two and 1 word of weight one that 1-cover B 1 (0) is called a partition of B 1 (0). Notice that if x and y are two different words in a partition of B 1 (0), then the intersection of the sets B 1 (x)∩B 1 (0) and B 1 (y)∩B 1 (0) is empty. A partition is called unavailable, if some of the words in the partition 1-cover words in other 1-balls containing faulty words. In what follows, we show that all partitions are not unavailable.

The number of all different partitions is equal to

n 2,2,...,2,1 m! = n! m! • 2 m , (7)
where the numerator is the usual multinomial coefficient and the number of 2's in it is equal to m. Notice that all the 1-balls of S that make partitions unavailable are centered at words of weights three or four, since words that are of weight at most two are not included in the 1-perfect code C and words of weight at least five cannot clearly make partitions unavailable. Hence, we consider the number of partitions that are made unavailable by a 1-ball of S centered at a word of weight three or four. Each 1-ball centered at a word of weight three that contains faulty words produces at most

3 2 n-2 2,2,...,2,1 (m -1)! + 3 1 n-1 2,2,...,2 m! = 3(n -2)! (m -1)! • 2 m-1 + 3(n -1)! m! • 2 m = 6(n -1)! m! • 2 m (8)
unavailable partitions. Each 1-ball centered at a word of weight four that contains faulty words produces at most

4 2 n-2 2,2,...,2,1 (m -1)! = 6(n -2)! (m -1)! • 2 m-1 = 6(n -1)! m! • 2 m (9)
unavailable partitions. Hence, by the equations ( 7), ( 8) and ( 9), the number of available partitions is at

least n! m! • 2 m -(k -1) • 6(n -1)! m! • 2 m .
Since k ≤ < n/6 + 1, the number of available partitions is positive. Thus, there exists a partition that is not unavailable. In conclusion, we need at most m + 1 = (n + 1)/2 queries to locate which of the m pairs of two words of weight one contain faulty words and whether there exist faulty words in the pair containing the last word of weight 1 and the word 0.

Assume now that a pair {e i1 , e i2 } contains faulty words, where i 1 , i 2 ∈ {1, 2, . . . , n} (e i defined as in the proof of Theorem 2.8). In order to conclude whether e i1 is a faulty word, we need a word e i1 + e j of weight two such that B 1 (e j ) \ {e i1 } contains no faulty vertices, i.e. e j is not included in any of the pairs containing faulty words in B 1 (x 1 ) and B 1 (e j ) does not intersect with any of the 1-balls of S other than B 1 (x 1 ). Now we have that the number of such words of weight two is at least

n -2( -k) - 4 2 (k -1).
Since < n/6 + 1, the previous number of words is positive. Hence, there exists a word of weight two satisfying the previous conditions. Assume then that the pair {0, e i } (i ∈ {1, 2, . . . , n}) contain faulty words. Using similar counting arguments as before, we can show that the faulty words can be found in this pair by at most two queries. In conclusion, we need at most two queries to locate the faulty words inside each pair containing them. If k = , then, by the previous considerations and by the fact that now we need only one query to identify the faulty word from a pair {e i1 , e i2 }, we need at most

c 1 (F n ) + • n + 1 2 + = c 1 (F n ) + • n + 3 2
queries to locate the faulty words in F n . If 1 ≤ k ≤ -1, then we also need at most

c 1 (F n ) + ( -1) • n + 1 2 + 2 ≤ c 1 (F n ) + • n + 3 2
queries. Thus, the claim follows. 2

Remark 2.10 It should be noted that the upper bound of the previous theorem can be sharpened to c 1 (F n ) + • (n + 1)/2. This slight improvement is obtained by more detailed considerations in the last paragraph of the proof (as pointed out by an anonymous referee).

Adaptive identification in square lattices

Let p and q be positive integers. The graph T p,q = (V, E) is a p × q torus in the square lattice, if the vertex set is

V = {(i, j) | 0 ≤ i ≤ p -1, 0 ≤ j ≤ q -1}
and the edge set is E = {((i, j), (i, j + 1)), ((i, j),

(i + 1, j)) | 0 ≤ i ≤ p -1, 0 ≤ j ≤ q -1},
where the first coordinate is calculated modulo p and the second coordinate is calculated modulo q (see Figure 2). Regular (r, ≤ )-identification in square lattice (or grid) have been studied, for example, in [START_REF] Ben-Haim | Exact minimum density of codes identifying vertices in the square grid[END_REF], [START_REF] Honkala | On identifying codes in the triangular and square grids[END_REF] and [START_REF] Honkala | On the density of identifying codes in the square lattice[END_REF]. Consider then adaptive (1, ≤ )-identification of T p,q . The case with = 1 is considered in [START_REF] Ben-Haim | Adaptive identification in graphs[END_REF][START_REF] Ben-Haim | Adaptive identification in graphs[END_REF]. If, on the other hand, ≥ 4, then it is easy to see that T p,q is not (1, ≤ )-identifiable. Hence, we concentrate on this subsection to the cases with = 2 and = 3.

The size of the 1-ball in T p,q is clearly 5, i.e. V 1 (T p,q ) = 5 (see Figure 2). By [START_REF] Golomb | Algebraic coding and the Lee metric[END_REF] and [START_REF] Golomb | Perfect codes in the Lee metric and the packing of polyominoes[END_REF], we know that there exists a 1-perfect code of T p,q , if both p and q are dividable by 5.

Consider then adaptive (1, ≤ 2)-identification in T p,q . By Theorem 2.1, we have the lower bound

a (1,≤2) (T p,q ) ≥ pq 5 + 3. (10)
The following theorem provides an upper bound for a (1,≤2) (T p,q ). Theorem 2.11 Let p and q be positive integers dividable by 5. If p ≥ 10 and q ≥ 10, then we have

a (1,≤2) (T p,q ) ≤ pq 5 + 6. (11)
Proof: The proof is similar to and even easier than the proof of Theorem 2.12. Therefore, the proof is omitted here. 2

Consider then adaptive (1, ≤ 3)-identification in T p,q . Again by Theorem 2.1, we have the lower bound

a (1,≤3) (T p,q ) ≥ pq 5 + 4. (12)
The following theorem provides an upper bound for a (1,≤3) (T p,q ). Theorem 2.12 Let p and q be positive integers dividable by 5. If p ≥ 15 and q ≥ 15, then we have

a (1,≤3) (T p,q ) ≤ pq 5 + 9. (13)
Proof: Assume p and q are positive integers dividable by 5. Let T p,q be a torus in the square lattice with pq vertices. Now there exists a 1-perfect covering C of T p,q . In what follows, we present a sketch of an adaptive (1, ≤ 3)-identifying algorithm:

1. For every c ∈ C ask the query Q 1 (c).

2. If all the queries output value 0, then there clearly exist no faulty vertices in T p,q .

3. If exactly one query output value 1, then this query 1-covers 1, 2 or 3 faulty vertices. Assume that this query is centered at the vertex (x, y). Then ask the queries

Q 1 (x, y+2), Q 1 (x+2, y), Q 1 (x, y- 2)
and Q 1 (x -2, y) (the first coordinate is calculated modulo p and the second is calculated modulo q). Depending on the answers of these queries, we need at most one auxiliary query to locate all the (from 1 to 3) faulty vertices in B 1 (x, y). Thus, we need at most 5 queries in this step.

4. Assume then that there exist two queries outputting 1. Assume first that the 1-balls of these queries are next to each other, i.e. assume that the queries outputting 1 are Q 1 (x, y) and Q 1 (x + 2, y + 1) (other cases are symmetrical). Now we need to locate the 1 or 2 faulty vertices in B 1 (x, y) without using queries that 1-cover vertices in B 1 (x + 2, y + 1). We start by asking the query Q 1 (x, y -1). If Q 1 (x, y -1) = 0, then the faulty vertices can be found using queries Q 1 (x -1, y -1), Q 1 (x, y + 2) and Q 1 (x + 1, y -1) as illustrated in Figure 3(a) (totally at most 4 queries).

Assume then Q 1 (x, y -1) = 1. Ask the query Q 1 (x -1, y + 1). If Q 1 (x -1, y + 1) = 1, then the faulty vertices can be easily found using totally at most 4 queries. Assume then

Q 1 (x-1, y+1) = 0. Ask the query Q 1 (x -1, y) (see Figure 3(b)). If Q 1 (x -1, y) = 1
, then the vertex (x, y) is faulty and we proceed by asking the query Q 1 (x + 1, y -1). If Q 1 (x + 1, y -1) = 0, then the vertex (x, y) is the only faulty one in B 1 (x, y) (totally 4 queries used). Otherwise, the second faulty vertex in B 1 (x, y) can be found by asking the query Q 1 (x -1, y -1) (totally 5 queries used).

We have still not considered the somewhat more problematic case when Q 1 (x -1, y) = 0. Now we know that the vertex (x, y -1) is faulty and that the vertices (x, y), (x -1, y) and (x, y + 1) are not faulty (see Figure 3(c)). However, there exists no fourth query telling whether the vertex (x + 1, y) is faulty, since queries 1-covering vertices in B 1 (x + 2, y + 1) cannot be used. Therefore, we proceed next by locating the faulty vertices in the 1-ball B 1 (x + 2, y + 1) using similar queries as with B 1 (x, y). (Indeed, the faulty vertices can be located from B 1 (x + 2, y + 1) using at most 5 queries, since we know that the vertices (x, y) and (x, y + 1) are not faulty.) After locating the faulty vertices in B 1 (x + 2, y + 1), we can also conclude whether the vertex (x + 1, y) is faulty or not. Hence, we use in this case at most 9 queries to locate all the faulty vertices in T p,q .

In other cases, we also proceed by finding the faulty vertices (or a faulty vertex) in B 1 (x + 2, y + 1) using similar queries as with B 1 (x, y). Notice that if there is only one faulty vertex in a 1-ball, then it can be located using 4 queries, and if there are two faulty vertices, then they can be located using 5 queries. Hence, in all the cases we need at most 9 queries to locate all the faulty vertices in T p,q .

It should also be noted that if the two queries outputting 1 after step 1 are not next to each other we can still use similar techniques to locate the faulty vertices using at most 9 queries.

5. Assume then that three queries in step 1 output value 1. Now each of these queries 1-cover exactly one faulty vertex. There are again several cases, but here we consider only one case as an example (others are analogous).

Assume that the queries outputting 1 are Q 1 (x, y), Q 1 (x -1, y + 2) and Q 1 (x + 2, y + 1). Ask then the query Q 1 (x -1, y -1) (see Figure 3(d)). If Q 1 (x -1, y -1) = 1, the faulty vertex can be found by the query Q 1 (x -2, y). Otherwise the faulty vertex can be located by asking the query Q 1 (x + 1, y -1) and depending on the answer we might need one auxiliary query. In conclusion, we need at most 3 queries to locate the faulty vertex in B 1 (x, y). Notice that these queries are chosen in such a way that they do not intersect with the balls B 1 (x -1, y + 2) and B 1 (x + 2, y + 1). Therefore, we need at most 9 queries to locate the faulty vertices in T p,q .

With any other choice of the queries outputting 1 in step 1, we can always found the faulty vertices using at most 9 queries.

In conclusion, the previous algorithm shows that a (1,≤3) (T p,q ) ≤ pq 5 + 9.

Fig. 3: The proof of Theorem 2.12 illustrated. The black and squared vertices respectively represent faulty and nonfaulty vertices. Moreover, at least one of the grey vertices is faulty. Furthermore, the dashed squares represent the asked queries.

Definition 1 . 1

 11 Let r and be positive integers. A codeC ⊆ V is said to be (r, ≤ )-identifying in G if for all X, Y ⊆ V such that |X| ≤ , |Y | ≤ and X = Y we have I r (C; X) = I r (C; Y ).If = 1, then we simply say that C is r-identifying. Remark 1.2 Let r and be positive integers. Then there exists an (r, ≤ )-identifying code C ⊆ V if and only if for all X, Y ⊆ V such that |X| ≤ , |Y | ≤ and X = Y we have B r (X) = B r (Y ).

Fig. 1 :

 1 Fig. 1: A 2-ball centered at the black vertex is illustrated in the torus T k 7,7 . Notice that the vertices in the border are wrapped around as suggested by the definition of the edge set E.

Fig. 2 :

 2 Fig. 2: A 1-ball centered at the black vertex is illustrated in the torus T7,7.

Acknowledgements

I wish to thank an anonymous referee for the insightful comments and suggestions. In particular, the sharpened result of Remark 2.10 is based on the referee's observation.

Adaptive weak identification

In this section, we introduce a concept of adaptive weak (r, ≤ )-identification, which enables the handling of larger . Similar concept has also been considered in the case of regular (r, ≤ )-identification. These weakly (r, ≤ )-identifying codes are considered, for example, in [START_REF] Honkala | On the identification of sets of points in the square lattice[END_REF].

Assume that during the execution of an algorithm we can fix a faulty vertex after one is found and then proceed with the algorithm. We call such an algorithm as adaptive weakly (r, ≤ )-identifying, if it can fix all the (at most ) faulty vertices. The minimum of the maximum number of queries needed in an adaptive weakly (r, ≤ )-identifying algorithm is denoted by a W (r,≤ ) (G), where G is the underlying graph. In what follows, we consider adaptive weak (r, ≤ )-identification in torii of king lattice T k p,q . The following theorem provides an upper bound for a W (r,≤ ) (T k p,q ), when p and q are dividable by 2r + 1.

Theorem 3.1 Let p and q be positive integers dividable by 2r + 1. If < min{p/(2r + 1), q/(2r + 1)}, then we have a W (r,≤ ) (T k p,q ) ≤ pq (2r + 1) 2 + (2 log 2 (2r + 1) + 1) .

Proof: Assume p and q are positive integers dividable by 2r +1. Let T k p,q be a torus in the king lattice with pq vertices. Now there exists an r-perfect code C of T k p,q . The following algorithm is adaptive weakly (r, ≤ 2)-identifying:

1. For every c ∈ C ask the query Q r (c).

2. If all the queries output value 0, then there clearly exist no faulty vertices in T k p,q . Let then the queries outputting value 1 be centered at v 1 , v 2 , . . . , v m with 1 ≤ m ≤ . In what follows, the first coordinate of a vertex is calculated modulo p and the second one is calculated modulo q. Choose then v j = (x j , y j ) to be such that there do not exist faulty vertices in B r (x j -2r, y j ), B r (x j -2r, y j +2r) and B r (x j , y j +2r). Indeed, such a vertex always exists since < min{p/(2r+ 1), q/(2r + 1)}. Now using some of the queries Q r (x j -2r, y j ), Q r (x j -2r + 1, y j ), . . . , Q r (x j -1, y j ) we can locate a column containing a faulty vertex by dichotomic search. Assume that this column is formed by the vertices {(x j + k, y j -r), (x j + k, y j -r + 1), . . . , (x j + k, y j + r)} with -r ≤ k ≤ r. The dichotomic search ensures that the found column is the leftmost of the columns containing faulty vertices in B r (v j ). Therefore, we can locate the faulty vertex in this column by dichotomic search using some of the queries Q r (x j + k -r, y j + 2r), Q r (x j + k -r, y j + 2r -1), . . . , Q r (x j + k -r, y j + 1). In conclusion, one faulty vertex in B r (v j ) can be identified using at most 2 log 2 (2r + 1) queries.

3. After locating the faulty vertex, we fix it and ask again the query Q r (v j ). Then we proceed as in the step 2.

In conclusion, the previous algorithm locates the faulty vertices using at most γ r (T k p,q ) + (2 log 2 (2r + 1) + 1)

queries. Thus, the claim follows.

As in the previous theorem, let p and q be positive integers dividable by 2r + 1. Consider then adaptive weak (r, ≤ )-identification in T k p,q with = p/(2r + 1). Let then the following sets be two patterns of faulty vertices in T k p,q :

) when the faulty vertices of T k p,q are X 1 , then Q r (v) = 1 when the faulty vertices of T k p,q are X 2 . The same also holds for the other direction. Hence, Q r (v) = 1 (v ∈ T k p,q ) with fault pattern X 1 if and only if Q r (v) = 1 with fault pattern X 2 . Thus, we cannot locate any faulty vertices in T k p,q . Similar considerations also apply when = q/(2r + 1). In conclusion, there does not exist any adaptive weakly (r, ≤ )-identifying code, if ≥ p/(2r + 1) or ≥ q/(2r + 1). Therefore, the bound on is the best possible in the previous theorem.


Sanming Zhou
email: smzhou@ms.unimelb.edu.au

On 4-valent Frobenius circulant graphs

Keywords: Circulant graph, double-loop network, Gaussian network, Frobenius graph, broadcasting

A 4-valent first-kind Frobenius circulant graph is a connected Cayley graph DLn(1, h) = Cay(Zn, H) on the additive group of integers modulo n, where each prime factor of n is congruent to 1 modulo 4 and

} with h a solution to the congruence equation x 2 + 1 ≡ 0 (mod n). In [A. Thomson and S. Zhou, Frobenius circulant graphs of valency four, J. Austral. Math. Soc. 85 (2008), 269-282] it was proved that such graphs admit 'perfect' routing and gossiping schemes in some sense, making them attractive candidates for modelling interconnection networks. In the present paper we prove that DLn(1, h) has the smallest possible broadcasting time, namely its diameter plus two, and we explicitly give an optimal broadcasting in DLn(1, h). Using number theory we prove that it is possible to recursively construct larger 4-valent first-kind Frobenius circulants from smaller ones, and we give a methodology for such a construction. These and existing results suggest that, among all 4-valent circulant graphs, 4-valent first-kind Frobenius circulants are extremely efficient in terms of routing, gossiping, broadcasting and recursive construction.

Introduction

Let n ≥ 5 be an integer whose prime factors are all congruent to 1 modulo 4. Then the congruence equation

x 2 + 1 ≡ 0 mod n (1)
is solvable (see e.g. [START_REF] Niven | An Introduction to the Theory of Numbers[END_REF][START_REF] Redmond | Number Theory[END_REF]). For a solution h to this equation, let

H = {[1], [h], -[1], -[h]}, (2)
where for an integer x, [x] denotes the residue class of x modulo n. Define DL n (1, h) to be the circulant graph with vertex set Z n such that [x], [y] ∈ Z n are adjacent if and only if [x-y] ∈ H. We call DL n (1, h) a 4-valent first-kind Frobenius circulant graph [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF][START_REF] Zhou | A class of arc-transitive Cayley graphs as models for interconnection networks[END_REF] of order n. It is known [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF]Theorem 2] that, for a fixed n = p e1 1 p e2 2 • • • p e l l such that p 1 , p 2 , . . . , p l ≡ 1 (mod 4), where p 1 , p 2 , . . . , p l are distinct prime factors of n and e 1 , e 2 , . . . , e l ≥ 1, there are precisely 2 l-1 pairwise non-isomorphic 4-valent first-kind Frobenius circulant graphs of order n. We remark that, if h is a solution to (1), then so is -h, and h and -h give rise to the same graph DL n (1, h).

The family of 4-valent first-kind Frobenius circulants was introduced in [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] in the context of optimal network design, and it was a subclass of a much larger class [START_REF] Fang | On orbital regular graphs and Frobenius graphs[END_REF][START_REF] Solé | The edge-forwarding index of orbital regular graphs[END_REF][START_REF] Zhou | A class of arc-transitive Cayley graphs as models for interconnection networks[END_REF] of arc-transitive graphs, called the first-kind Frobenius graphs (see the next section for definition). The importance of such graphs lies in that they admit 'perfect' routing and gossiping schemes under the store-and-forward, all-port and full-duplex model (see [START_REF] Zhou | A class of arc-transitive Cayley graphs as models for interconnection networks[END_REF] for detail). In the special case of 4-valent first-kind Frobenius circulants, this means that DL n (1, h) achieves the smallest possible edge-forwarding index and admits a shortest path routing which is optimal for the edge, arc, minimal-edge and minimal-arc forwarding indices [START_REF] Heydemann | Cayley graphs and interconnection networks[END_REF] simultaneously. Moreover, under the store-and-forward, all-port and full-duplex model, DL n (1, h) has the smallest possible gossiping time and admits an optimal gossiping scheme under which messages are always transmitted along shortest paths, and at any time every arc is used exactly once for message transmission. (See [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF]Theorem 3] for detail.) Because of these 4-valent first-kind Frobenius circulants are strong candidates for modelling interconnection networks. Such graphs are also useful in coding theory, and they were studied independently in [START_REF] Martínez | Perfect codes for metrics induced by circulant graphs[END_REF] from a coding-theoretic point of view by using the language of Gaussian integers. Combining [START_REF] Martínez | Perfect codes for metrics induced by circulant graphs[END_REF]Theorem 4] and the discussion in [START_REF] Thomson | Frobenius graphs as interconnection networks[END_REF], it follows that the family of 4-valent first-kind Frobenius circulants is precisely the family of Gaussian graphs [START_REF] Martínez | Perfect codes for metrics induced by circulant graphs[END_REF]Definition 3] of odd orders (see Lemma 5 and Remark 6).

The purpose of this paper is to study broadcasting in and recursive construction of 4-valent first-kind Frobenius circulants. We prove that such a graph achieves the smallest possible broadcasting time, namely its diameter plus two (Theorem 4). With the help of number theory we prove that it is possible to recursively construct larger 4-valent first-kind Frobenius circulants from smaller ones, and we give a methodology for such a construction (Section 4). These results make 4-valent first-kind Frobenius circulants even more attractive for modelling interconnection networks, besides their applications in coding theory. There is a long history in studying 4-valent circulants (also called double-loop networks) as models for networks; see e.g. [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF][START_REF] Hwang | A complementary survey on double-loop networks[END_REF][START_REF] Hwang | A survey on multi-loop networks[END_REF] for surveys. The results in this paper and [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] suggests that, among all 4-valent circulants, 4-valent first-kind Frobenius circulants are exceedingly efficient in terms of routing, gossiping, broadcasting and recursive construction.

The reader is referred to [START_REF] Dixon | Permutation Groups[END_REF] for group-theoretic terminology used in this paper.

Preliminaries

In this section we collect a few results on 4-valent first-kind Frobenius circulants that will be used in later sections.

Given a group X with identity element 1 and a subset S ⊆ X \ {1} such that s -1 ∈ S for every s ∈ S, the Cayley graph Cay(X, S) is defined to have vertex set X such that x, y ∈ X are adjacent if and only if xy -1 ∈ S.

A Frobenius group is a transitive permutation group with the property that there are nonidentity elements fixing one point but only the identity element can fix two points. It is well known [START_REF] Dixon | Permutation Groups[END_REF] that a finite Frobenius group is a semidirect product K H, where K is a nilpotent normal subgroup, and we may think of K H as acting on K in such a way that K acts on K by right multiplication and H acts on K by conjugation. A first-kind K H-Frobenius graph is defined [START_REF] Fang | On orbital regular graphs and Frobenius graphs[END_REF][START_REF] Zhou | A class of arc-transitive Cayley graphs as models for interconnection networks[END_REF] as a Cayley graph Cay(K, a H ) on K, for some a ∈ K such that a H = K, where a H is the H-orbit containing a and either H is of even order or a is an involution. There is another class of graphs, called the second-kind Frobenius graphs [START_REF] Fang | On orbital regular graphs and Frobenius graphs[END_REF], associated with finite Frobenius groups. The reader is referred to [START_REF] Fang | Gossiping and routing in second-kind Frobenius graphs[END_REF] for gossiping and routing properties of second-kind Frobenius graphs.

Let

Z * n = {[u] : 1 ≤ u ≤ n -1, gcd(n, u) = 1} be the multiplicative group of units of ring Z n . Then Aut(Z n ) ∼ = Z *
n and Z * n acts on Z n by the usual multiplication:

[x][u] = [xu], [x] ∈ Z n , [u] ∈ Z * n . The semidirect product Z n Z * n acts on Z n such that [x] ([y],[u]) = [(x + y)u] for [x], [y] ∈ Z n and [u] ∈ Z * n . We use [u] -1 to denote the inverse element of [u] in Z * n . The operation of Z n Z * n is defined by ([x 1 ], [u 1 ])([x 2 ], [u 2 ]) = ([x 1 ] + [x 2 ][u 1 ] -1 , [u 1 u 2 ]) for ([x 1 ], [u 1 ]), ([x 2 ], [u 2 ]) ∈ Z n Z * n . Thus the inverse element of ([x], [u]) in Z n Z * n is (-[xu], [u] -1 ). A graph G is called X-arc-transitive if X is
a group of automorphisms of G such that any arc of G can be permuted to any other arc of G by an element of X, where an arc is an ordered pair of adjacent vertices.

Lemma 1 ( [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF]) Let n ≥ 5 be an integer all of whose prime factors are congruent to 1 modulo 4. Let h be a solution to [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF] and H be as given in [START_REF] Dixon | Permutation Groups[END_REF].

Then H = [h] is a cyclic subgroup of Z * n , Z n H is a Frobenius group, and DL n (1, h) is a Z n H-arc-transitive first-kind Z n H-Frobenius graph.
In fact, by [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF]

, gcd(h, n) = 1 and [h] 2 = -[1]. Hence [h] = {[1], [h], [h] 2 , [h] 3 } = H ≤ Z * n .
The last two statements in the lemma follow from [18, Theorem 2]. We may represent DL n (1, h) by a plane tessellation of squares [START_REF] Hwang | A survey on multi-loop networks[END_REF][START_REF] Wong | A combinatorial problem related to multimodule memory organizations[END_REF][START_REF] Yebra | The diameter of undirected graphs associated to plane tessellations[END_REF] such that the square with coordinates (x, y) represents the vertex [x + yh] of DL n (1, h) (see Figure 1). Thus the squares adjacent to For 0 ≤ i ≤ r, define [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] x

i = max{x ≥ 0 : d([0], [x + ih]) = x + i}. Note that x 0 = r. Let A = {[j + kh] : 1 ≤ j ≤ x k , 0 ≤ k ≤ r}.
The image of A under the action of H is given by

AH = {[j + kh], [-k + jh], [-j -kh], [k -jh] : 1 ≤ j ≤ x k , 0 ≤ k ≤ r}.
Equivalently, AH intersects with the four quadrants at A, A[h], -A, -A[h], respectively, and H permutes these four parts cyclically (see Figure 1), where

A[h] = {[j + kh][h] : [j + kh] ∈ A}, -A = {[-j -kh] : [j + kh] ∈ A} and -A[h] = {[-j -kh][h] : [j + kh] ∈ A}. (Note that [j + kh][h] = [-k + jh] and [-j -kh][h] = [k -jh] by (1).) AH ∪ {[0]
} is an algebraic expression [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] of the minimum distance diagram [START_REF] Hwang | A survey on multi-loop networks[END_REF][START_REF] Wong | A combinatorial problem related to multimodule memory organizations[END_REF][START_REF] Yebra | The diameter of undirected graphs associated to plane tessellations[END_REF] of DL n (1, h) as shown by the following lemma.

Lemma 2 ([18, Lemma 7]) With the notation above, the following hold:

(a) for

[j + kh] ∈ A, d([0], [j + kh]) = d([0], [-k + jh]) = d([0], [-j -kh]) = d([0], [k -jh]) = j + k; (b) the diameter d of DL n (1, h) is given by d = max{x k + k : 0 ≤ k ≤ r}; (c) AH = Z n \ {[0]}
with S = {[a], [b], -[a], -[b]}.
Lemma 3 ([12, Theorem 6], see also [START_REF] Thomson | Frobenius graphs as interconnection networks[END_REF]) Let n ≥ 5 be an integer all of whose prime factors are congruent to 1 modulo 4. Let h be a solution to [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF]. Let 0 < a < b be the unique primitive solution of (3) such that ah ≡ b (mod n). Then r = (a + b -1)/2 (4) and, for 0 ≤ i ≤ r, x i = max{r -i, r -a}.

(

) 5
In particular, the diameter of DL n (1, h) is given by

d = x r + r = b -1.

Broadcasting time

A common process in communication networks is to disseminate a message from a specific source vertex to all other vertices in such a way that in each time step any vertex who has received the message already can retransmit it to at most one of its neighbours. This process is called broadcasting, and the minimum number of time steps required is denoted by b(G, u) if G is the network and u is the source vertex. The broadcasting time [START_REF] Hromkovič | Dissemination of information in interconnection networks (broadcasting and gossiping)[END_REF] of G, denoted by b(G), is defined to be the maximum among b(G, u) for u running over V (G). In general, it is difficult to determine b(G). See [7, Section 5.2] for a survey.

The maximum order of a connected 4-valent circulant graph with a given diameter d ≥ 2 is n d = 2d 2 + 2d + 1 [START_REF] Yebra | The diameter of undirected graphs associated to plane tessellations[END_REF], and up to isomorphism DL n d (1, 2d + 1) is the unique connected 4-valent circulant graph [START_REF] Yebra | The diameter of undirected graphs associated to plane tessellations[END_REF] with diameter d and order n d . It was noticed in [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] that DL n d (1, 2d + 1) was a first-kind Frobenius circulant. In [START_REF] Liestman | Network properties of double and triple fixed step graphs[END_REF]Theorem 1] it was proved that b(DL n d (1, 2d+1)) = d+2. By using a similar methodology we obtain the following result which generalises [START_REF] Liestman | Network properties of double and triple fixed step graphs[END_REF]Theorem 1] to all 4-valent first-kind Frobenius circulants.

Theorem 4 Let n ≥ 5 be an integer all of whose prime factors are congruent to 1 modulo 4. Let h be a solution to [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF] and d the diameter of DL n (1, h) (as given in Lemmas 2 and 3). Then

b(DL n (1, h)) = d + 2.
Moreover, we can explicitly give an optimal broadcasting in DL n (1, h).

Proof: Denote G = DL n (1, h). Since G is vertex-transitive, b(G) = b(G, [u]) for all [u] ∈ Z n .
Without loss of generality we may assume that [0] has a message to be broadcasted in G. In the following we prove

b(G, [0]) = d + 2 and so establish b(G) = d + 2. Part 1: Initially, the message is at [0]. A broadcasting is defined by specifying a pair L([u]) = (t u , [v u ]) (6)
for each

[u] = [0], which means that [u] receives the message at time t u from a neighbour [v u ] of [u]. We require t v < t u for [v] = [v u ] since [v] should receive the message before retransmitting it to [u]. We also require (t u , [v u ]) = (t w , [v w ]) whenever [u] = [w]
since no vertex is allowed to send the message to two of its neighbours at the same time.

Let r be as in [START_REF] Fang | Gossiping and routing in second-kind Frobenius graphs[END_REF]. We successively send the message to the vertices in the negative x-direction at times 1, 2, . . . , r, in the x-direction at times 2, 3, . . . , r + 1, in the y-direction at times 3, 4, . . . , r + 2, and in 49 4 50 3 51 2 52 1 0 0 1 2 2 3 3 4 4 5 19 5 20 5 21 4 22 3 23 3 24 4 25 For 0 ≤ j ≤ r, define

y j = max{k : 1 ≤ k ≤ r, x k ≥ j}. Let δ ij = 1 if i = j and δ ij = 0 otherwise. Define L([-j]) = (j, [-(j -1)]), L([j]) = (j + 1, [j -1]), 1 ≤ j ≤ r (7) L([kh]) = (k + 2, [(k -1)h]), 1 ≤ k ≤ r (8) L([-kh]) = (k + 3, [-(k -1)h]), 1 ≤ k ≤ min{r, d -1} (9)
L([j

+ kh]) = (j + k + 2 -δ jr , [j + (k -1)h]), 1 ≤ j ≤ r, 1 ≤ k ≤ y j (10) L([-k + jh]) = (j + k + 1 -δ kr , [-k + (j -1)h]), 1 ≤ k ≤ r, 1 ≤ j ≤ x k (11) L([-j -kh]) = (j + k + 2 -δ jr , [-j -(k -1)h]), 1 ≤ j ≤ r, 1 ≤ k ≤ y j (12) L([k -jh]) = (j + k + 3 -δ kr , [k -(j -1)h]), 1 ≤ k ≤ r, 1 ≤ j ≤ x k , j + k < d. (13)
In this way we define a broadcasting on all vertices of G other than those

[k -jh] ∈ -A[h] (that is, 0 ≤ k ≤ r, 1 ≤ j ≤ x k ) in the fourth quadrant such that d([0], [k -jh]) = j + k = d. Consider the remaining vertices above. Such a vertex [k -jh] must satisfy j = x k (for otherwise d([0], [k -(j + 1)h]) = j + k + 1 = d + 1 by Lemma 2 (a), which is a contradiction) and hence is of the form [k -x k h], where x k + k = d and x k ≥ 1. By Lemma 2 (b) and (5), if a < r, then d = x r + r = 2r -a ≥ r + 1, and [r -x r h] is the only element of -A[h] whose distance to [0]
is d and hence is the only exceptional vertex to be considered. In this case, if x r = 1, then since [r] receives the message at time r

+ 1 = d, we may define L([r -x r h]) = (d + 1, [r]); if x r ≥ 2, then since L([r-(x r -1)h]) = (d+1, [r-(x r -2)h]) by (13), we may define L([r-x r h]) = (d+2, [r-(x r -1)h]).
Thus, if a < r, then [r -x r h] with x r + r = d receives the message at time d + 1 or d + 2. This together with ( 7)-( 13) gives a broadcasting in G using d + 2 time steps. See Figure 2 for this broadcasting in DL 53 [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF]23). It remains to deal with the case a = r. In this case, x i = r -i for 0 ≤ i ≤ r by ( 5), d = r by Lemma 2 (b), and so

[k -x k h] = [k -(d -k)h] is an exceptional vertex for each k = 0, 1, . . . , d. Moreover, since a = r = (a + b -1)/2, we have b = a + 1 = d + 1, n = a 2 + b 2 = 2d 2 + 2d + 1 and so G = DL n d (1, 2d + 1
) by the discussion after Theorem 4. Thus, h = 2d + 1 and

[(d + 1)h] = [d]. This implies [k -x k h] = [k -(d -k)h] = [-(d -k) + kh + h] and hence [k -x k h] is adjacent to [-(d -k) + kh]. However, by (11), [-(d -k) + kh] received the message at time d + 1 -δ d-k,d for 0 ≤ k ≤ d -1. Thus, we may define L([k -x k h]) = (d + 2 -δ d-k,d , [-(d -k) + kh]) for 0 ≤ k ≤ d -1. Note that [d -x d h] = [d]
received the message at time d + 1 (see [START_REF] Hromkovič | Dissemination of information in interconnection networks (broadcasting and gossiping)[END_REF]). So we have finished defining a broadcasting in G using d + 2 time steps when a = r. See Figure 3 for an illustration of this broadcasting.

In summary, we have proved b(G, [0]) ≤ d + 2 up to now.

Part 2: We now prove that d + 2 is a lower bound for b(G, [0]). This is true when d = 1 since in this case G is the complete graph

K 5 = DL 5 (1, 2). Assume d ≥ 2 in the following. Since the minimum distance diagram is symmetric, each of A, A[h], -A, -A[h] contains at least one vertex whose distance to [0] is d. Let [u] ∈ A be at distance d from [0]. Then [uh] ∈ A[h], [-u] ∈ -A, [-uh] ∈ -A[h] all have distance d to [0]
. Suppose to the contrary that there exists a broadcasting using d + 1 time steps. One of the neighbours

[1], [h], [-1], [-h] of [0]
should receive the message at time 1, and assume that the other three neighbours receive the message at times t 1 < t 2 < t 3 respectively, where t 1 ≥ 2. Note that

[uh 0 ] = [u], [uh 1 ] = [uh], [uh 2 ] = [-u], [uh 3 ] = [-uh] by (1). Let P i : [0], [v i ], [w i ], . . . , [uh i ] be the path of G along which the message is sent from [0] to [uh i ], where [v i ] ∈ {[1], [h], [-1], [-h]}, i = 0, 1, 2, 3. Since d([0], [uh i ]) = d, each P i has length at least d. We may have [v i ] = [v j ] for distinct i and j. Since t 2 ≥ 3, t 3 ≥ 4, if [v i ]
receives the message at time t 2 or t 3 , then the last vertex [uh i ] of P i receives the message at time d + 2 or later, which is a contradiction. Similarly, if t 1 ≥ 3, then no [v i ] receives the message at time t 1 . Hence each [v i ] receives the message at time

1 or t 1 = 2. If, for i = j, both [v i ] and [v j ] receive the message at time 2, then [v i ] = [v j ]
and one of [uh i ] and [uh j ] receives the message at time d + 2 or later, a contradiction. Hence at most one of

[v 0 ], [v 1 ], [v 2 ], [v 3 ]
receives the message at time 2 and the remaining three or four vertices receive the message at time 1. Suppose without loss of generality that An optimal broadcasting for any source vertex [w] can be obtained from the optimal broadcasting L in Part 1 for source vertex [0] by translation. Define

[v 0 ], [v 1 ], [v 2 ] receive the message at time 1. Then [v 0 ] = [v 1 ] = [v 2 ]
L w ([u + w]) = (t u , [v u + w]) for each [u] ∈ Z n , where (t u , [v u ]
) is as in [START_REF] Heydemann | Cayley graphs and interconnection networks[END_REF]; that is, the time when the message originated from [w] is sent from [v u + w] to [u + w] is the same as the time when the message originated from

[0] is sent from [v u ] to [u] under L. Since [x] → [x + w], [x] ∈ Z n , is an automorphism of G, L w above defines a broadcasting for source vertex [w], and it is optimal since b(G, [w]) = b(G, [0]) = d + 2. 2
In the special case of DL n d (1, 2d + 1) the broadcasting described in Part 1 of the proof above is similar to the one given in [START_REF] Liestman | Network properties of double and triple fixed step graphs[END_REF]. Nevertheless, this is by no means the only optimal broadcasting in DL n d (1, 2d + 1). In general, optimal broadcastings of DL n (1, h) other than the one given in the proof of Theorem 4 can be found by using similar approaches.

Recursive construction

An important issue in network design is whether it is possible to 'expand' an existing network to larger ones of similar structures. And if this is possible, how can we construct efficiently such larger networks from smaller ones? For instance, an attractive feature of hypercubes is that we can easily expand a given hypercube to larger ones of higher dimensions. In this section we prove that 4-valent Frobenius circulants share this property. We will give algorithms for constructing larger 4-valent Frobenius circulants from smaller ones by using number theory. To this end we will use an equivalent definition of a 4-valent Frobenius circulant in terms of Gaussian integers.

A Gaussian integer is a complex number a + bi with both a and b in Z. (In this section we reserve i for the imaginary unit of complex numbers.) The set Z[i] of all Gaussian integers is a ring under the usual addition and multiplication of complex numbers, the ring of Gaussian integers. Its units are 1, -1, i and -i, and for α ∈ Z[i] and a unit ε we call εα an associate of α. It is well known that Z[i] is an Euclidean domain with the norm function defined by N (a + bi) = a 2 + b 2 for 0 = a + bi ∈ Z[i]. In other words, for any α, β ∈ Z[i] with β = 0, there exists γ, δ ∈ Z[i] such that α = γβ + δ and either δ = 0 or N (δ) < N (β). Hence Z[i] is a principal ideal domain and so a unique factorization domain. It is easy to see that N (αβ) = N (α)N (β) for any nonzero α, β ∈ Z[i]. All these results and definitions about Gaussian integers can be found in, for example, [START_REF] Ireland | A Classical Introduction to Modern Number Theory[END_REF].

Given Theorem 2]. In the case when gcd(a, b) = 1, the Gaussian graph G α generated by α is defined [START_REF] Martínez | Perfect codes for metrics induced by circulant graphs[END_REF] to have vertex set

0 = α = a + bi ∈ Z[i], let Z[i] α = Z[i]/(α) denote the quotient ring of Z[i] with respect to the principal ideal (α) of Z[i]. Denote by [β] α = β + (α) the residue class modulo α containing β. For β, γ ∈ Z[i], define [12] d α ([β] α , [γ] α ) to be the minimum value of |x|+|y| such that [β -γ] α = [x+yi] α . Then d α is a metric in Z[i] α [12,
Z[i] α such that [β] α , [γ] α are adjacent if and only if d α ([β] α , [γ] α ) = 1. In other words, G α is the Cayley graph Cay(Z[i] α , H α ) on the additive group of Z[i] α , where H α = {[1] α , -[1] α , [i] α , -[i] α }. (14)
Note that, if α is an associate of 1 + i (that is, N (α) = 2), then the cardinality of H α is 2 and so G α is 2-valent. In general, G α is a 4-valent graph as long as gcd(a, b) = 1 and α is not an associate of 1 + i.

One can verify that G α ∼ = G εα for any unit ε of Z[i], and

Z[i] α → Z[i] εα , [β] α → [εβ]
εα defines an isomorphism between the two graphs. Since εα = a + bi, -a -bi, -b + ai, b -ai when ε runs over the four units of Z[i], in studying Gaussian graphs we may assume without loss of generality that both a and b are positive integers. Gaussian graphs above were introduced in [START_REF] Martínez | Perfect codes for metrics induced by circulant graphs[END_REF] with motivation from coding theory. It turns out that in the case when N (α) = a 2 + b 2 is odd, they are exactly the family of 4-valent Frobenius circulants. This was first noticed by Alison Thomson (personal communication). It is implied in the following lemma in which N (α) can be odd or even.

Lemma 5 (a) Let

0 = α = a + bi ∈ Z[i] be such that a, b > 0, gcd(a, b) = 1 and N (α) > 2. Then G α ∼ = DL N (α) (1, l)
, where l is the unique solution to

x 2 + 1 ≡ 0 (mod N (α)) such that al ≡ b (mod N (α)).
φ : Z N (α) → Z[i] α , [x + yl] → [x + yi] α , (15)
where [x + yl] is the residue class of x + yl modulo N (α).

We claim that φ is a well-defined mapping. In fact, if x+y ≡ x +y l (mod

N (α)), then a(x-x )+ b(y -y ) ≡ 0 (mod N (α)) since al ≡ b (mod N (α)). Thus a(x -x ) + b(y -y ) = s(a 2 + b 2 )
for some s ∈ Z. The only solutions to this Diophantine equation are x -x = sa + bt, y -y = sb -at for t ∈ Z. Hence (x -x ) + (y -y )i = (s -ti)α and so (iii) That n is even can occur, but in this case the corresponding 5) is a primitive solution to x 2 + y 2 = 34 and the corresponding l is 13 as 3 • 13 ≡ 5 (mod 34) and 13 2 + 1 ≡ 0 (mod 34). However, since [START_REF] Martínez | Perfect codes for metrics induced by circulant graphs[END_REF], - [START_REF] Dixon | Permutation Groups[END_REF] and - [START_REF] Niven | An Introduction to the Theory of Numbers[END_REF] are not in Z * 34 , by [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF]Lemma 4], { [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF], [START_REF] Martínez | Modeling toroidal networks with the Gaussian integers[END_REF], - [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF], - [START_REF] Martínez | Modeling toroidal networks with the Gaussian integers[END_REF]} is not regular on Z 34 \ {[0]} and so DL 34 [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF][START_REF] Martínez | Modeling toroidal networks with the Gaussian integers[END_REF] is not a Frobenius graph.

[x + yi] α = [x + y i] α . It is clear that φ is surjective. Suppose [x + yi] α = [x + y i] α . Then (x -x ) + (y -y )i = (c + di)(a + bi) for some c + di ∈ Z[i]; that is, x -x =
DL n (1, l) is not a first-kind Frobenius circulant because the subgroup {[1], [l], -[1], -[l]} of Z * n is not regular on Z n \ {[0]}. For example, (3,
The set H α defined in ( 14) is a subgroup of the group Z[i] * α of units of ring Z[i] α . One can verify that (x+yi) i s = (x+yi)i s defines an action (as a group) of H α on the additive group of Z[i] α , where x+yi, i s and (x + yi)i s are interpreted as their residue classes modulo α. Hence Z[i] α H α is well-defined and moreover it acts on Z[i] α (as a set) by

(x + yi) (c+di,i s ) = ((x + c) + (y + d)i)i s , x + yi ∈ Z[i] α , (c + di, i s ) ∈ Z[i] α H α ,
where the Gaussian integers involved are interpreted as their residue classes modulo α. One can verify that Z[i] α H α preserves adjacency and non-adjacency of G α . So it can be regarded as a group of automorphisms of G α . Moreover, by [21, Lemma 2.1] and the fact that the group H α is transitive on the connection set H α of G α , we have

Lemma 7 Every Gaussian graph G α is Z[i] α H α -arc-transitive.
When N (α) is odd this is known in [START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] in view of Lemmas 1 and 5. In this case one can prove that

Z[i] α H α is a Frobenius group.
To construct larger 4-valent Frobenius circulants from smaller ones, by Lemma 5 it suffices to find an approach to constructing larger Gaussian graphs of odd order from smaller ones. The following lemma serves for this purpose, and it applies to a broader family of graphs. Note that for any

0 = α = a + bi ∈ Z[i] we can define G α = Cay(Z[i] α , H α ) as before without requiring gcd(a, b) = 1
, where H α is as in [START_REF] Niven | An Introduction to the Theory of Numbers[END_REF]. To ensure G α is a nontrivial graph with valency 4, we require that α is not a unit or an associate of 2 or 1 + i, or equivalently N (α) ≥ 5. Such generalized Gaussian graphs were studied in [START_REF] Martínez | Modeling toroidal networks with the Gaussian integers[END_REF] (but with the necessary condition N (α) ≥ 5 neglected).

A graph G 1 is called a cover of a graph G 2 if there exists a surjective mapping φ :

V (G 1 ) → V (G 2 ) such that for each u ∈ V (G 1 ), the restriction of φ to the neighbourhood N G1 (u) of u in G 1 is a bijection from N G1 (u) to the neighbourhood N G2 (φ(u)) of φ(u) in G 2 . We say that G 1 is a k-fold cover of G 2 if in addition k = |φ -1 (v)| for all v ∈ V (G 2 ). Lemma 8 Let α, β ∈ Z[i] be such that N (α), N (β) ≥ 5.
Then G αβ can be constructed from G α and is an N (β)-fold cover of G α .

Proof: Let K = ([α] αβ ) be the principal ideal of Z[i] αβ induced by [α] αβ . Since Z[i] is Euclidean, its elements are of the form ξ = ηβ + δ with δ = 0 or N (δ) < N (β). Hence K = {[αδ] αβ : δ ∈ Z[i], δ = 0 or N (δ) < N (β)}. Since K = (α)/(αβ)
, when it is viewed as a subgroup of the additive group of

Z[i] αβ , we have Z[i] α ∼ = Z[i] αβ /K via the classical isomorphism [ξ] α → K +[ξ] αβ , [ξ] α ∈ Z[i] α . Hence |K| = N (αβ)/N (α) = N (β).
Now we construct G αβ from G α as follows. Consider an arbitrary pair of adjacent vertices [START_REF] Solé | The edge-forwarding index of orbital regular graphs[END_REF] Note that this adjacency relation is defined for all pairs of adjacent vertices

[ξ] α , [ξ ] α of G α . By the definition of G α , there exist η ∈ Z[i] and a unit ε of Z[i], both relying on ξ and ξ , such that ξ -ξ = αη + ε. Construct a graph Ĝαβ with vertex set Z[i] αβ such that each [αδ + ξ] αβ ∈ K + [ξ] αβ is adjacent to [αδ + ξ -ε] αβ = [α(δ + η) + ξ ] αβ ∈ K + [ξ ] αβ and [αδ + ξ] αβ is not adjacent to any other element in K + [ξ ] αβ .
[ξ] α , [ξ ] α of G α . Since ξ -ξ = -αη -ε, when interchanging the roles of [ξ] α and [ξ ] α in (16), we obtain that [αδ + ξ -ε] αβ = [α(δ + η) + ξ ] αβ is adjacent to [α(δ + η) + ξ + ε] αβ = [αδ + ξ] αβ in Ĝαβ .
Hence the adjacency relation ( 16) is symmetric. Moreover, it is independent of the choice of representatives of [ξ] α and Therefore, G αβ is identical to Ĝαβ and so can be constructed from G α as in the previous paragraph. It is obvious that the quotient graph of G αβ with respect to the partition Note that αβ = (ac-bd)+(ad+bc)i gives rise to the solution (ac-bd, ad+bc) to x 2 +y 2 = np e . We claim that this is a primitive solution. Suppose otherwise. Then there exists a prime q in Z which divides both ac -bd and ad + bc. If q divides a, then it divides both bd and bc. Since q cannot divide b due to gcd(a, b) = 1, it follows that q divides both c and d, which contradicts the assumption gcd(c, d) = 1. So q is not a divisor of a. Similarly, q is not a divisor of b, c or d. Since q divides ac -bd and ad + bc, it divides c(ac-bd)+d(ad+bc) = a(c 2 +d 2 ) = ap e and a(ac-bd)+b(ad+bc) = c(a 2 +b 2 ) = cn. Since q divides neither a nor c, it follows that q divides p e and n, and hence q = p is a prime factor of n, which contradicts our assumption. Therefore, (ac-bd, ad+bc) is a primitive solution to x 2 +y 2 = np e . It is clear that there is a unique unit ε 1 of Z

[αδ + ξ] αβ . In fact, if [αδ 1 + ξ 1 ] αβ = [αδ + ξ] αβ (which implies [ξ 1 ] α = [ξ] α ), then ξ 1 = ξ + α(σβ + δ -δ 1 ) for some σ ∈ Z[i] and hence ξ 1 -ξ = α(σβ + δ -δ 1 + η) + ε. Thus, by (16), [αδ 1 + ξ 1 ] αβ ∈ K + [ξ] αβ is adjacent to [α(δ 1 + (σβ + δ -δ 1 + η)) + ξ ] αβ = [α(δ + η) + ξ ] αβ ∈ K + [ξ ] αβ ,
Z[i] αβ /K of Z[i] αβ is isomorphic to G α ,
[i] such that ε 1 αβ = a 1 + b 1 i satisfies a 1 , b 1 > 0. Then (a 1 , b 1 ) is a nonnegative primitive solution to x 2 + y 2 = np e . Moreover, G ε1αβ ∼ = G αβ and so G ε1αβ is constructed from G α via G αβ . (

Concluding remarks

In this paper we proved that 4-valent first-kind Frobenius circulants have the minimum possible broadcasting time, namely their diameter plus two, and we explicitly gave optimal broadcasting in such graphs. We developed an approach to constructing larger 4-valent first-kind Frobenius circulants from smaller ones by using number theory. Our results in this regard can be easily generalised to Gaussian graphs of even order.

As mentioned in the introduction, if n ≥ 5 has l distinct prime divisors and all of them are congruent to 1 modulo 4, then there are exactly 2 l-1 pairwise non-isomorphic 4-valent first-kind Frobenius circulants of order n [18, Theorem 2].

Question 15 What is the minimum diameter among such 2 l-1 graphs of a given order n?

As mentioned earlier, there is a one-to-one correspondence between solutions h to x 2 + 1 ≡ 0 mod n and nonnegative primitive solutions (a, b) to x 2 + y 2 = n with 0 < a < b and ah ≡ b mod n. Since

Fig. 1 :

 1 Fig. 1: Plane tessellation of DL53(1, 23). The area bounded by the red lines is the minimum distance diagram AH ∪ {[0]}, where A = {[1], [2], [3], [4], [24], [25], [26], [47], [48], [17], [18], [40], [41]} is the part of AH in the first quadrant. The other three parts A[h], -A, -A[h] of AH are obtained by rotating A about the origin by 90 • , 180 • , 270 • respectively. For this graph we have d = 6, r = x0 = 4, x1 = 3, x2 = x3 = x4 = 2, a = 2, b = 7 and n = 53 = 2 2 + 7 2 .

  [x + yh] represent [x + 1 + yh] (right), [x -1 + yh] (left), [x + (y + 1)h] (above) and [x + (y -1)h] (below), respectively. Denote by d([x], [y]) the distance in DL n (1, h) between [x] and [y]. Define [18] r = max{x ≥ 0 : d([0], [x]) = x}.

Fig. 2 :

 2 Fig. 2: An optimal broadcasting in DL53(1, 23). Subscripts represent the times that the corresponding vertices receive the message originated from [0]. The part in the first quadrant bounded by bold lines is A.

5 Fig. 3 :

 53 Fig. 3: An optimal broadcasting in DL41(1, 9). Subscripts represent the times that the corresponding vertices receive the message originated from [0]. The part bounded by bold lines is A, and the other three parts of the minimum distance diagram are obtained by rotating A about the origin by 90 • , 180 • , 270 • respectively. DL41(1, 9) is the largest connected 4-valent circulant graph with diameter d = 4. We have a = b -1 = r = d = x0 = 4, x1 = 3, x2 = 2, x3 = 1, x4 = 0 and n = 41 = 5 2 + 4 2 . Notice that [5], [15], [25], [35] receive the message from [37], [6], [16], [26] at times 5, 6, 6, 6 respectively.

  and one of [u], [uh], [-u] receives the message at time d + 3 or later. This final contradiction proves that b(G, [0]) is at least d + 2. Combining Parts 1 and 2, we obtain b(G, [0]) = d + 2 and so b(G) = d + 2. Hence the broadcasting given in Part 1 is optimal for source vertex [0].

(

  b) Conversely, for any solution l to x 2 + 1 ≡ 0 (mod n), we have DL n (1, l) ∼ = G α , where α = a + bi with a, b > 0 the unique nonnegative primitive solution to x 2 + y 2 = n such that al ≡ b (mod n). Proof: (a) Since a 2 + b 2 = N (α) and gcd(a, b) = 1, by [15, Theorem 6.4], there exists a unique solution l to x 2 + 1 ≡ 0 (mod N (α)) such that al ≡ b (mod N (α)). Define

2

 2 ac -bd and y -y = ad + bc. Hence a(x -x ) + b(y -y ) ≡ 0 (mod N (α)). Since gcd(a, b) = 1, we have gcd(a, N (α)) = 1 and so aa ≡ 1 (mod N (α)) for some a ∈ Z. Using al ≡ b (mod N (α)), we then have aa (x -x ) + aa l(y -y ) ≡ 0 (mod N (α)) and so x + yl ≡ x + y l (mod N (α)). Therefore, φ is injective and hence bijective. Since φ([1]) = [1] α and φ([l]) = [i] α , one can see that φ is an isomorphism from DL N (α) (1, l) to G α . (b) Given a solution l to x 2 + 1 ≡ 0 (mod n),by [15, Theorem 6.5] there is a unique primitive solution a, b > 0 to x 2 + y 2 = n such that al ≡ b (mod n). Similar to the proof above, one can verify DL n (1, l) ∼ = G α , where α = a + bi. Remark 6 (i) In part Lemma 5 (a), there exists a unique solution l to x 2 + 1 ≡ 0 (mod N (α)) such that bl ≡ a (mod N (α)). Since gcd(a, N (α)) = gcd(b, N (α)) = 1, from al ≡ b, bl ≡ a (mod N (α)) we have ll ≡ 1 (mod N (α)). Since l 4 ≡ 1 (mod N (α)), it follows that l ≡ l 3 ≡ -l (mod N (α)) and so DL n (1, l) = DL n (1, l ). Thus we may assume 0 < a < b in (a) without loss of generality. Similarly, we may assume 0 < a < b in Lemma 5 (b). (ii) It is known that the Diophantine equation x 2 + y 2 = n has a nonnegative primitive solution if and only if every odd prime factor of n is congruent to 1 modulo 4 (see e.g. [15, Corollary 6.8.2 and pp.320]). In the case when N (α) is odd in (a) and n is odd in (b) of Lemma 5, DL N (α) (1, l) is a 4-valent first-kind Frobenius graph. Hence the family of 4-valent first-kind Frobenius circulants is identical to the family of Gaussian graphs of odd orders.

  which agrees with[START_REF] Solé | The edge-forwarding index of orbital regular graphs[END_REF] applied to [αδ + ξ] αβ . Therefore, Ĝαβ is well-defined as an undirected graph. Since G α is 4-valent, by its definition Ĝαβ is 4-valent as well. We now prove that it is exactly the generalized Gaussian graph G αβ . Using the notation above, obviously [αδ + ξ] αβ and [αδ + ξ -ε] αβ are adjacent in G αβ . Thus, by (16), if two vertices are adjacent in Ĝαβ , then they are adjacent in G αβ . Conversely, suppose [ζ] αβ and [ζ ] αβ are adjacent in G αβ . Then ζ -ζ = τ (αβ) + ε for some τ ∈ Z[i] and a unit ε of Z[i]. Since Z[i] is Euclidean, we can write ζ = αδ + ξ and ζ = αδ + ξ , where ξ = 0 or N (ξ) < N (α), and ξ = 0 or N (ξ ) < N (α). Thus [αδ + ξ] αβ = [αδ + ξ ] αβ + [ε] αβ . Since [ζ] αβ = [αδ + ξ] αβ and [ζ ] αβ = [αδ + ξ ] αβ = [αδ + ξ -ε] αβ , by the definition of Ĝαβ , [ζ] αβ and [ζ ] αβ are adjacent in Ĝαβ .

2 Remark 13

 213 See the discussion following[START_REF] Niven | An Introduction to the Theory of Numbers[END_REF].) From Lemma 5 (a) it follows that DL np e (1, h 1 ) with h 1 defined in Step 4 is a 4-valent first-kind Frobenius circulant. Similarly, α β = (ac + bd) + (-ad + bc)i gives rise to a primitive solution (ac -bd, ad + bc) to x 2 + y 2 = np e , and hence DL np e (1, h 2 ) with h 2 given in Step 4 is a 4-valent first-kind Frobenius circulant. To prove DL np e (1, h 1 ) ∼ = DL np e (1, h 2 ), it suffices to prove G αβ ∼ = G α β , or equivalently DL np e (acbd, ad + bc) ∼ = DL np e (ac + bd, -ad + bc) by Lemma 5 and the comments before Lemma 3. Suppose otherwise. Then there exists k ∈ Z coprime to np e such that {[ac -bd] np e , [ad + bc] np e } = [k] np e • {[ac + bd] np e , [-ad + bc] np e }, where [x] np e is the residue class in Z containing x modulo np e . If [ac -bd] np e = [k(ac + bd)] np e and [ad + bc] np e = [k(-ad + bc)] np e , then there exists γ∈ Z[i] such that αβ = (αβ)(αβ)γ + k(α β), that is, β = (ᾱβγ + k) β. Thus N (β) = N (ᾱβγ + k)N ( β) = N (ᾱβγ + k)N (β). Hence N (ᾱβγ + k) = 1 and ᾱβγ + k is a unit of Z[i]. It follows that β = c + di = c -di, -c + di, d + ci or -d -ci; that is, d = 0, c = 0, c = d or c = -d,which violates the assumption gcd(c, d) = 1. If [ac -bd] np e = [k(-ad + bc)] np e and [ad + bc] np e = [k(ac + bd)] np e , then there exists γ ∈ Z[i] such that αβ = (αβ)(αβ)γ + ki(ᾱβ), that is, α = (α βγ + ki)ᾱ. Thus α βγ + ki is a unit of Z[i] and so b = 0, a = 0, a = b or a = -b, which contradicts gcd(a, b) = 1. Combining Procedures 9 and 10, we have a well understood mechanism to 'expand' a graph in the family of 4-valent first-kind Frobenius circulants to a larger one in the same family. Example 14 In the case when p = 5, by Procedure 9 we recursively obtain h(1) = 2, h(2) = 7, h(3) = 57, . . . and K 5 = DL 5 (1, 2) ∼ = G 1+2i , DL 5 2 (1, 7) ∼ = G 4+3i , DL 5 3 (1, 57) ∼ = G 11+2i , . . . Similarly, for p = 13 we have h(1) = 5, h(2) = 70, h(3) = 239, . . . and DL 13 (1, 5) ∼ = G 3+2i , DL 13 2 (1, 70) ∼ = G 5+12i , DL 13 3 (1, 239) ∼ = G 9+46i , . . . Using Procedure 10 and the computation above, we can construct two 4-valent first-kind Frobenius circulants of order, say, 5 3 • 13 2 = 21125. We first compute (11 + 2i)(5 + 12i) = 31 + 142i and (11 + 2i)(5 -12i) = 79 -122i. From the former we obtain 31 2 + 142 2 = 5 3 • 13 2 and the unique h > 0 satisfying 31h ≡ 142 and h 2 + 1 ≡ 0 (mod 5 3 • 13 2 ) is h = 8182. Hence DL 5 3 •13 2 (1, 8182) ∼ = G 31+142i is a first-kind Frobenius circulant. For 79 -122i we use its associate i(79 -122i) = 122 + 79i. We have 122 2 + 79 2 = 5 3 • 13 2 and the unique h > 0 satisfying 122h ≡ 79 and h 2 + 1 ≡ 0 (mod 5 3 • 13 2 ) is h = 18182. Hence DL 5 3 •13 2 (1, 18182) ∼ = G 122+79i ( ∼ = DL 5 3 •13 2 (1, 8182)) is a first-kind Frobenius circulant. Both DL 5 3 •13 2 (1, 8182) and DL 5 3 •13 2 (1, 18182) can be constructed from DL 5 3 (1, 57) or DL 13 2 (1, 70) by using the method in the proof of Lemma 8, and they are 13 2 -fold covers of DL 5 3 (1, 57) and 5 3 -fold covers of DL 13 2 (1, 70).

  and each element of Z n \ {[0]} appears exactly once in AH.

	It is well known (e.g. [15, Corollary 6.8.2]) that the Diophantine equation
	x 2 + y 2 = n	(3)
	is solvable if and only if the canonical factorization of n into primes contains no factor p e with e odd and
	p ≡ 3 (mod 4). An integral solution (a, b) to (3) is called primitive if gcd(a, b) = 1. It is known [15,
	Theorem 6.4] that every nonnegative primitive solution (a, b) of (3) determines a unique solution h of (1)
	such that ah ≡ b (mod n), and different nonnegative primitive solutions determine different h modulo
	n. Conversely, if h is a solution of (1), then there is [15, Theorem 6.5] a nonnegative primitive solution
	(a, b) of (3) such that ah ≡ b (mod n). Obviously, for such (a, b) we have gcd(a, n) = gcd(b, n) = 1
	and the mapping [x] → [ax], [x] ∈ Z n is an isomorphism from DL n (1, h) to DL n (a, b), the latter being
	the circulant graph Cay(Z n , S)

  5 26 6 27 6 28 5 29 4 30 4 31 5 32 6 33 7 34 7 42 6 43 6 44 5 45 4 46 4 47 5 48 6 5 6 6 5 7 5 8 6 9 7 10 8 11 8

	39 6 40 7 41 8
	15 5 16 5 17 6 18 7
	35 7 36 6 37 6 38 7
	12 8 13 7 14 7

  and moreover G αβ is an N (β)-fold cover of G α . 2We now give procedures for constructing larger 4-valent first-kind Frobenius circulants from smaller ones. The case below for prime power orders is a straightforward application of relevant results in number theory. (The uniqueness of DL p e (1, h(e)) follows from[START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] Theorem 2].) The unique 4-valent first-kind Frobenius circulant DL p e (1, h(e)) of order p e , for every integer e ≥ 1, where h(e) is a solution to x 2 + 1 ≡ 0 (mod p e ). Frobenius circulants as we will see below. By Lemma 8 each graph in this sequence is a cover of the graphs preceding it. We notice that the 'smallest' graph DL p (1, h(1)) in the sequence is exactly C(p; ±1, ±h(1)) in [5, Theorem 1.2(c)], which plays a significant role in the classification [5, Theorem 1.2] of a family of arc-transitive graphs.The following procedure deals with the case of composite integers. A 4-valent first-kind Frobenius circulant DL n (1, h), defined by an integer n ≥ 5 with all prime factors congruent to 1 modulo 4 and a solution h to (1); a prime p ≡ 1 (mod 4) which is not a divisor of n; and an integer e ≥ 1. Find the unique nonnegative primitive solution (a, b) to (3) such that ah ≡ b (mod n), and set α = a + bi;2. find a nonnegative primitive solution (c, d) to x 2 + y 2 = p e , and set β = c + di;3.construct G αβ and G α β based on G α by using rule (16);4. let ε 1 be the unique unit of Z[i] such that ε 1 αβ = a 1 + b 1 i satisfies a 1 , b 1 > 0, and ε 2 the unique unit of Z[i] such that ε 2 α β = a 2 + b 2 i satisfies a 2 , b 2 > 0;find the unique solution h j to x 2 + 1 ≡ 0 (mod np e ) such that a j h j ≡ b j (mod np e ), j = 1, 2;5.construct DL np e (1, h 1 ) and DL np e (1, h 2 ).

	Procedure 9 Input: A prime p ≡ 1 (mod 4). 1. By the well-known Lagrange Theorem, h(1) ≡ ((p -1)/2)! (mod p); this gives DL p (1, h(1)); 2. suppose DL p e (1, h(e)) has been constructed for some e ≥ 1, we construct DL p e+1 (1, h(e + 1)) by using h(e + 1) = h(e) + p e w (see e.g. [14, Section 2.6]), where w is a solution to the congruence equation 2h(e)x ≡ -(h(e) 2 + 1)/p e (mod p). The graphs DL p (1, h(1)), DL p 2 (1, h(2)), . . . , DL p e (1, h(e)), DL p e+1 (1, h(e + 1)), . . . (17) thus constructed are both interesting and important because they are building blocks for constructing all Input: Output: Two non-isomorphic 4-valent first-kind Frobenius circulants of order np e obtained by expanding DL n (1, h). 1. 4-valent first-kind Procedure 10 Remark

Output: 11 We may use standard algorithms in number theory to find (a, b) in Step 1 and h j in Step 4. See for example the proofs of [15, Theorems 6.4 and 6.5]. We may obtain (c, d) in Step 2 by recursively computing h(e) in Procedure 9 and then applying the algorithm implied in the proof of [15, Theorem 6.5]. Theorem 12 Procedure 10 is correct, that is, DL np e (1, h 1 ) and DL np e (1, h 2 ) above are 4-valent firstkind Frobenius circulants, and moreover DL np e (1, h 1 ) ∼ = DL np e (1, h 2 ). Proof: Using the notation above, we have DL n (1, h) ∼ = G α by Lemma 5. Since p ≡ 1 (mod 4), the Diophantine equation x 2 + y 2 = p e has exactly two nonnegative primitive solutions. (This can be deduced from, say, [15, Corollaries 6.5.1 and 6.8.1].) Thus (c, d) in Step 2 exists and the other nonnegative primitive solution is (d, c).

Acknowledgements

The author appreciates the referees for their helpful comments and Alison Thomson for bringing [12,13] to his attention. He is supported by a Future Fellowship (FT110100629) of the Australian Research Council. Part of the work was done during his visit to Shanghai University where he was supported by a Shanghai Leading Academic Discipline Project (No. S30104).

by Lemma 3 the diameter of DL n (1, h) is equal to b -1, the question above is equivalent to the one of finding the smallest b -1 among all such solutions (a, b).

For example, when n = 65 = 5 • 13, both h 1 = 8 and h 2 = 18 are solutions to x 2 + 1 ≡ 0 mod 65, and the corresponding nonnegative primitive solutions to x 2 + y 2 = 65 such that 0 < a j < b j and a j h j ≡ b j mod 65 are (a 1 , b 1 ) = (1, 8) and (a 2 , b 2 ) = (4, 7). Since 65 has only two distinct prime divisors, DL 65 [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF][START_REF] Hwang | A complementary survey on double-loop networks[END_REF] and DL 65 [START_REF] Bermond | Distributed loop computer networks: a survey[END_REF][START_REF] Thomson | Frobenius circulant graphs of valency four[END_REF] are the only non-isomorphic 4-valent first-kind Frobenius circulants of order 65, and the answer to Question 15 is 6 when n = 65.