Counting Small Cycles in Generalized de Bruijn Digraphs Toru Hasunuma and Yukio Shibata Department of Computer Science, Gunma University, 1-5-1 Tenjin-cho, Kiryu, Gunma, 376 Japan In this paper, we count small cycles in generalized de Bruijn digraphs. Let n Å pd h , where d É/ p, and gl Å gcd(d l 0 1, n). We show that if p õ d 3 and k ° logd n / 1, or p ú d 3 and k ° h / 3, then the number of cycles of length k in a generalized de Bruijn digraph GB (n, d) is given by 1/ k (l Ék m(k/l)gl d l / gl , where m is the Möbius function and r denotes the smallest integer not smaller than a real number r. q 1997 John Wiley & Sons, Inc. 1. INTRODUCTION In parallel processing or distributed computing, the choice of the topology of an interconnection network is very important, because the topology of the interconnection network is one of the critical factors which determines the performance of the system. Now, the hypercube is widely used as a topology of an interconnection network. However, one of the disadvantages of the hypercubes is the fact that the degree increases with its size. As another topology which is suitable for an interconnection network, the de Bruijn digraph is noticed. The de Bruijn digraphs are bounded degree networks, i.e., one can increase the size keeping a fixed degree. The de Bruijn digraphs have good properties such as small diameter, high connectivity, and easy routing. Also, the de Bruijn digraph has more vertices than does the hypercube for the same degree and the same diameter. From these points, the de Bruijn digraph is noticed as a competitor of the hypercube (see [1]). One of the shortcomings of de Bruijn digraphs is the restriction on the number of vertices, i.e., the order of a de Bruijn digraph is a power of an integer. A de Bruijn digraph is denoted by B(d, D). Then, the order of B(d, D) is d D . Generalized de Bruijn digraphs generalize the order to any integer, keeping the good properties of de Bruijn digraphs. Generalized de Bruijn digraphs were in- dependently proposed by Imase and Itoh [6], and Reddy et al. [11]. A generalized de Bruijn digraph is denoted by GB (n, d). A de Bruijn digraph B(d, D) is also a generalized de Bruijn digraph represented by GB (d D , d). In generalized de Bruijn digraphs, the numbers of loops [3, 10], closed walks [13], spanning trees, and Eulerian tours [8] have been counted. In this paper, we count small cycles in generalized de Bruijn digraphs. Let n Å pd h , where d É/ p, and gl Å gcd(d l 0 1, n). We show that if p õ d 3 and k ° logd n / 1, or p ú d 3 and k ° h / 3, then the number of cycles of length k in GB (n, d) is given by SD k 1 gl ∑m k l Ék l dl gl , where m is the Möbius function and r is the smallest integer not smaller than a real number r. For the counting of small cycles, the de Bruijn digraph was studied in [9]. Our results generalize the number of loops in generalized de Bruijn digraphs [3, 10] and the number of small cycles in de Bruijn digraphs [9]. Since cycles (or rings) are fundamental structures, embeddability of a cycle in an interconnection network is a basic subject from the point of network simulation. Also, fault-tolerance is an important subject in interconnection NETWORKS, Vol. 29 (1997) 39–47 q 1997 John Wiley & Sons, Inc. CCC 0028-3045/97/010039-09 39 / 8u0d$$0005 11-15-96 17:06:07 netwa W: Networks 743 40 HASUNUMA AND SHIBATA networks. From these points, fault-tolerant embeddability of a cycle in interconnection networks is an interesting problem. For example, the problem of embeddability of a cycle in de Bruijn networks was studied in [12]. The number of cycles of a certain length in an interconnection network gives insight into the fault-tolerant embeddability of a cycle of the length in the interconnection network. Thus, counting cycles is an interesting subject from both theoretical and practical points of view. The numbers of loops (cycles of length 1) and digons (cycles of length 2) have another useful meaning. Generalized de Bruijn digraphs are models of interconnection networks whose links are unidirected. We often consider interconnection networks whose links are bidirected. In this case, we consider the undirected version of generalized de Bruijn digraphs. Generalized de Bruijn graphs are obtained from generalized de Bruijn digraphs by replacing each arc by the corresponding edge (undirected arc), deleting loops, and replacing multiedges by single edges. In the undirected version of GB (n, d), the degree of a vertex which had a loop is 2d 0 2 and the degree of a vertex which was contained in a digon is 2d 0 1. (For any other vertex, the degree is 2d.) Thus, a vertex which had a loop in the digraph has a free degree of two and a vertex which was contained in a digon has a free degree of one. These free degrees could be used to connect outside and/or inside of the system. Thus, the numbers of loops and digons are important information for such a case. As a corollary of our counting, the numbers of loops and digons in generalized de Bruijn digraphs are explicitly given. 2. DEFINITION AND NOTATION Let m and n be integers. The greatest common divisor of m and n is denoted by gcd(m, n). If m divides n, then we write mÉn. Otherwise, we write m É/ n. Let r be a real number. Then, r and r stand for the greatest integer not greater than r and the smallest integer not smaller than r, respectively. In this paper, a digraph may have loops and multiarcs. Let G be a digraph. The vertex set of G and the arc set of G are denoted by V (G) and E(G), respectively. Suppose that e Å (u, £ ) √ E(G). Then, it is said that u is adjacent to £ and £ is adjacent from u. Also, it is said that e is incident to £ and e is incident from u. Suppose that e1 Å (x, y), e2 Å (y, z) √ E(G). Then, it is said that e1 is adjacent to e2 and that e2 is adjacent from e1 . Let £ √ V (G). The multiset of vertices which are adjacent from £ in G is denoted by G( £ ). A walk of G whose length is k ¢ 1 is an alternate sequence of vertices and arcs defined as follows: £0 e0£1 e1rrrek01£k , / 8u0d$$0005 11-15-96 17:06:07 netwa Fig. 1. where ei is incident from £i and incident to £i/1 for 0 ° i õ k. Here, vertices and arcs are not necessarily distinct. It is sufficient to write only arcs when there is no confusion. It is also sufficient to write only vertices when G has no multiarcs. A walk whose vertices are distinct is called a path. If £0 Å £k , then it is called a closed walk. A closed walk whose vertices are distinct except for £k is called a cycle. We consider closed walks as sequences. The number of closed walks in a digraph does not mean the cardinality of the set of closed walks in the digraph, but the number of the equivalence classes of closed walks with respect to rotation. For example, consider the digraph in Figure 1. Then, the cardinality of the set of cycles of length 3 is three, and the number of cycles of length 3 is one. Let w be a walk. The length of w is denoted by ÉwÉ. The set of vertices and the set of arcs of w are denoted by V (w) and E(w), respectively. For a closed walk w Å £0 e0£1 e1rrrek01£0 , if there exists an integer 0 õ l õ k such that ei (mod k ) Å ei/l (mod k ) for 0 ° i õ k, then we call w a periodic closed walk. Otherwise, we call w a nonperiodic closed walk. Suppose that m is the cardinality of the set of nonperiodic closed walks of length k in G. Then, the number of nonperiodic closed walks of length k in G is m/k because the cardinality of each equivalence class with respect to rotation is k. The line digraph of G denoted by L(G) is defined as follows: H V ( L(G)) Å E(G), E(L(G)) Å {(e1 , e2 )É e1 is adjacent to e2 ; e1 , e2 √ E(G)}. The operation that induces L(G) from G is referred to the line digraph operation to G. For fundamental properties of the line digraphs, see [5]. W: Networks 743 COUNTING SMALL CYCLES IN DE BRUIJN DIGRAPHS 41 The generalized de Bruijn digraph GB (n, d) is defined as follows: H V (GB (n, d)) Å {0, 1, . . . , n 0 1}, E(GB (n, d)) Å {(x, y)É y å dx / i(mod n), 0 ° i õ d}. If there exists an integer D ¢ 0 such that n Å d D , then GB (n, d) Å B(d, D). For some properties of generalized de Bruijn digraphs such as connectivity, embeddability, and routing, see [3]. Fig. 2. 3. NONPERIODIC CLOSED WALKS In this section, we study the relation between nonperiodic closed walks and cycles with respect to the line digraph operation. Definition 3.1. Let w Å £0 e0£1 e1rrrek01£0 be a nonperiodic closed walk of length k ¢ 1 in a digraph. If w is a cycle, then h(w) is 01. If w is not a cycle and the arcs ei ’s are distinct for 0 ° i õ k, then h(w) is 0. Otherwise, h(w) is defined as follows: h(w) Å max 0°iõk 0õlõk HZ m ei/j (mod k ) Å ei/j/l (mod k ) for 0 ° j õ m, ei/m (mod k ) x ei/m/l (mod k ) . J . If h(w) ú 0, then h(w) is the maximum length of a subwalk which arises at at least two different positions on w. Since w is nonperiodic, h(w) õ ÉwÉ. If h(w) õ m ° ÉwÉ, then any subwalk of length m of w is unique. Definition 3.2. Let C(G) be the set of cycles in a digraph G. If there are two cycles which have a common vertex of G such that their arc sets are distinct, then the twisted girth u(G) of G is defined as follows: u(G) Å {É E(c1 ) < E(c2 ) É É min c1,c2√ C (G ) V ( c1 ) > V ( c2 ) x M, E(c1 ) x E(c2 )}. Otherwise, let u(G) be ` . Let c1 and c2 be cycles in G such that V ( c1 ) > V ( c2 ) x M, E(c1 ) x E(c2 ) and É E(c1 ) < E(c2 )É Å u(G). The common sequence of c1 and c2 is denoted by c1 > c2 . [Since É E(c1 ) < E(c2 )É Å u(G), c1 and c2 have a unique common sequence.] Suppose that c1 Å x0 e0rrres01 x0 , c2 / 8u0d$$0005 11-15-96 17:06:07 netwa Å y0 f0rrrft01 y0 and c1 > c2 Å x0 e0rrrel01 xl Å y0 f0rrrfl01 yl (see Fig. 2). Now let z Å x0 e0rrres01 x0 e0rrrel01 xl flrrrft01 x0 . Then, z is a nonperiodic closed walk such that É E(z)É Å u(G) and ÉzÉ Å h(z) / u(G). Let w be a nonperiodic closed walk in G with h(w) ¢ 0. Then, there exist two cycles in w whose arc set are distinct such that they go through a common vertex. Thus, É E(w)É ¢ u(G). Therefore, if u(G) x ` , then the twisted girth of G is the minimum cardinality of arc sets of nonperiodic closed walks in G which are not cycles. Thus, u(G) ¢ 2. There is the following relation between h(w) and u(G): Lemma 3.3. Let G be a digraph. Let w be a nonperiodic closed walk in G such that h(w) ¢ 0. Then, ÉwÉ ¢ h(w) / u(G). Also, this bound is sharp. Proof. Let w be a nonperiodic closed walk in a digraph G such that h(w) ¢ 0. Since u(G) is the minimum cardinality of arc sets of nonperiodic closed walks in G which are not cycles, É E(w)É ¢ u(G). Therefore, it is sufficient to prove ÉwÉ ¢ h(w) / É E(w)É if h(w) ¢ 0. We employ the induction on the length of w. Let ÉwÉ Å 1. Then, w is a loop and h(w) Å 01. Thus, the proposition is vacantly satisfied. Let ÉwÉ ú 1. If h(w) Å 0, then all arcs of w are distinct; thus, ÉwÉ Å É E(w)É. Suppose that h(w) ú 0. Let w Å £0 g0£1 g1rrrgÉwÉ01£0 . From the definition of h(w), there exist integers i and l such that W: Networks 743 42 HASUNUMA AND SHIBATA i.e., É E(g0rrrgr01 )É ° d. Thus, É E(w)É Å É E(g0rrr gl01 )É ° l 0 r / d. Therefore, the proposition holds. CASE 2.2.2. d ú r: In this case, ÉwÉ Å h(w) 0 r / d. Thus, Éwl/l Å h(w)/l . The sequence gh(w)0rrrrgh(w)/l01 can be rewritten in the next two ways: Fig. 3. H g0rrrgl01 g0rrrgr 01 , g0rrrgd01 g0rrrgd01rrrg0rrrgd01 g0rrrgl/r 01 (mod d ) . gi/j (modÉwÉ) Å gi/j/l (modÉwÉ) , 0 ° j õ h(w), gi/h (w ) (modÉwÉ) x gi/h (w ) /l (modÉwÉ) . Without loss of generality, we can set i Å 0 and l õ ÉwÉ/2 . Thus, H Let w * Å g0rrrgd01 . Also, let w 9 Å g0rrrge01 be the nonperiodic part of w *. (Any closed walk has a unique nonperiodic part.) That is, w * consists of several iterations of w 9 such that w 9 is nonperiodic. (If w * is nonperiodic, then w 9 Å w *.) Then, the sequence gh(w ) 0rrrrgh(w ) /l01 can be also rewritten as follows: gj Å gj /l (modÉwÉ) , 0 ° j õ h(w), g0rrrge01 g0rrrge01rrrg0rrr gh(w ) x gh(w ) /l (modÉwÉ) . ge01 g0rrrgl/r 01 (mod e ) . CASE 1. h( w ) ° l : Let x Å g0 g1rrrgh(w ) 01 and y Å gl gl/1rrrgl/h (w ) 01 . Since l ° ÉwÉ/2 , l / h(w) ° ÉwÉ. Therefore, x and y have no intersection as subwalks of w. However, E(x) Å E(y). Thus, ÉwÉ ¢ h(w) / É E(w)É. CASE 2. h(w) ú l: Let s Å g0 g1rrrgh(w ) /l01 (modÉwÉ) . Then, s can be rewritten as follows (see Fig. 3): g0rrrgl01 g0rrrgl01rrrg0rrrgl01 g0rrrgr 01 , where r Å h(w)(mod l), i.e., s consists of several iteration of the sequence g0rrrgl01 followed by the sequence g0rrrgr 01 . Therefore, ÉsÉ Å h(w) / l ¢ h(w) / É E(s)É. When s Å w, the proposition clearly holds. CASE 2.1. ÉsÉ õ ÉwÉ: Let w 0 s be the remaining subsequence of w by deleting s from w. Then, clearly, Éw 0 sÉ ¢ É E(w 0 s)É. Therefore, ÉwÉ Å ÉsÉ / Éw 0 sÉ ¢ h(w) / É E(s)É / É E(w 0 s)É ¢ h(w) / É E(w)É. CASE 2.2. ÉsÉ ú ÉwÉ: In this case, h(w) õ ÉwÉ õ h(w) / l. Let d å ÉwÉ(mod l). CASE 2.2.1. d õ r: In this case, ÉwÉ Å h(w) / l 0 r / d. The sequence gh(w ) /l0rrrrgh(w ) /l01 can be rewritten in the next two ways: g0rrrgr 01 , g0rrrgd01 g0rrrgd01rrrg0rrrgd01 g0rrrgr 01 (mod d ) , / 8u0d$$0005 11-15-96 17:06:07 netwa Thus, É E(g0rrrgl01 )É Å e, i.e., É E(w 9 )É Å É E(w)É. If l å 0(mod e ), then w must be periodic. Therefore, / 0(mod e ). Since gl01 (mod e ) is adjacent to g0 , h(w 9 ) lå ¢ 0. Also, gi Å gi/l (mod e ) for 0 ° i õ r. Thus, h(w 9 ) ¢ r. By the induction hypothesis, Éw 9É ¢ r / É E(w 9 )É. Therefore, Éw *É ¢ r / É E(w)É. Now, Éw *É Å ÉwÉ 0 ÉwÉ/l r l and r Å h(w) 0 h(w)/l r l. Since ÉwÉ/ l Å h(w)/l , ÉwÉ ¢ h(w) / É E(w)É. The sharpness is shown by considering the nonperiodic j closed walk z defined above for this lemma. Let w Å £0 e0£1 e1rrrek01£0 be a closed walk in a digraph G. Let L(w) denote a closed walk in L(G) mapped from w by the line digraph operation to G, i.e., L(w) Å e0 e1rrrek01 e0 . [By the property of the line digraph operation, L(G) contains no multiarc. Thus, L(w) can be represented by the sequence of only the vertices of L(G).] Clearly, ÉwÉ Å É L(w)É, and if w is a nonperiodic closed walk, then L(w) is a nonperiodic closed walk. Also, for any nonperiodic closed walk x in L(G), there exists a nonperiodic closed walk y in G such that L(y) Å x. [Let x Å f0 f1rrrfl01 f0 , where fi Å (ui , ui/1 ) √ E(G) Å V ( L(G)). Then, y Å u0 f0u1 f1rrrfl01ul .] Therefore, the numbers of nonperiodic closed walks of certain length in G and L(G) are equal. [Similarly, the numbers of periodic closed walks of certain length in G and L(G) are equal.] In other words, the number of nonperiodic closed walks of certain length is invariant under the line digraph operation. However, as shown in the following lemma, the ratio of the number of cycles of length k to the number of nonperiodic closed walks of length k increases by the line digraph operation. W: Networks 743 COUNTING SMALL CYCLES IN DE BRUIJN DIGRAPHS 43 Lemma 3.4. Let w be a nonperiodic closed walk in a digraph. Then, h(L(w)) Å H h(w) 0 1 if h(w) ¢ 0, 01 if h(w) Å 01. Proof. Let w be a nonperiodic closed walk. If w is a cycle, then, clearly, L(w) is a cycle, i.e., h(L(w)) Å 01 if h(w) Å 01. Suppose that w is not a cycle. Let s Å u0 f0u1 f1rrrfl01ul be a subwalk of w such that s x w. Let Lw (s) be a subwalk of L(w) which is mapped from s by the line digraph operation. Then, Lw (s) Å f0 f1rrrfl01 . [Note that Lw (s) is not always equal to L(s). For example, if ul Å u0 , then L(s) Å f0 f1rrrfl01 f0 .] Thus, É Lw (s)É Å ÉsÉ 0 1. If ÉsÉ Å h(w), then É Lw (s)É Å h(L(w)). Therefore, h(L(w)) Å h(w) 0 1 if h(w) ¢ 0. j From Lemma 3.4, if the number of iterations of the line digraph operation exceeds a certain value, the number of nonperiodic closed walks of length k becomes equal to the number of cycles of length k. Theorem 3.5. The number of nonperiodic closed walks of length k in a digraph G is equal to the number of cycles of length k in L m (G) if m ¢ k 0 u(G) / 1. Proof. We first consider the case u(G) Å ` . In this case, all nonperiodic closed walks are cycles. [if h(w) ¢ 0 for a closed walk w in G, then É E(w)É ¢ u(G).] Since a cycle is transformed to a cycle by the line digraph operation, the proposition clearly holds. Then, we consider the case u(G) x ` . Let w be a nonperiodic closed walk of length k in G such that w is not a cycle. From Lemma 3.4, h(L m (w)) Å 01 if m ¢ h(w) / 1. From Lemma 3.3, h(w) ° ÉwÉ 0 u(G) Å k 0 u(G). Thus, if m ¢ k 0 u(G) / 1, then L m (w) is a cycle. In other words, all nonperiodic closed walks of length k in G are transformed to cycles of length k in j L m (G) if m ¢ k 0 u(G) / 1. 4. COUNTING In this section, we count small cycles in generalized de Bruijn digraphs, applying the results in the previous section. First, we study the value of u(G): Lemma 4.1. u(GB (n, d)) ° logd n / 2. Proof. Let d k ° n õ d k/ 1 , i.e., k Å logd n . Let G (0) Å {0} and G i (0) Å <£ √ G i01( 0 ) G( £ ), for i ú 0. Let A and B be multisets. The number of elements which are equal to a in A is denoted by NA (a). Then, A can be represented by the function NA . We define A 0 B by defining NA0B as follows: NA0B (a) Å max(0, NA (a) 0 / 8u0d$$0005 11-15-96 17:06:07 netwa Fig. 4. 0 NB (a)), i.e., A 0 B denotes the relative complement of B in A. For example, let A Å {a, b, b, b} and B Å {b, b, c}. Then, A 0 B Å {a, b}. Now, G(0) 0 {0} Å {1, 2, . . . , d 0 1}, G 2 (0) 0 G(0) Å {d, d / 1, . . . , d 2 0 1}, : G k/ 1 (0) 0 G k (0) Å {d k , d k / 1, . . . , 0, . . . , d k/ 1 0 1(mod n)}. For any vertex £ √ G i (0) 0 G i0 1 (0), i ú 0, there exists a vertex u √ G i0 1 (0) 0 G i0 2 (0) such that u is adjacent to £ [where we assume G 01 (0) Å 0/ for convenience] (see Fig. 4). Therefore, the vertex 0 is contained in a cycle of length k / 1 since 0 √ G k/ 1 (0) 0 G k (0) and ( G i (0) 0 G i0 1 (0)) > ( G j (0) 0 G j 0 1 (0)) Å 0/ for 0 ° i õ j ° k. On the other hand, the vertex 0 has a loop. Therefore, there are a loop and a cycle of length k / 1 such that they contain the vertex 0. Hence, u(GB (n, d)) ° k / 2 Å logd n / 2. j Lemma 4.2. H u(GB (n, d)) Å 2 B n õ d u(GB (n, d)) Å 3 B d ° n õ d 2 . Proof. Let n õ d. From Lemma 4.1, u(GB (n, d)) ° 2. Thus, u(GB (n, d)) Å 2. Conversely, let u(GB (n, d)) Å 2. Then, there exist multiloops, i.e., there is a vertex £ such that { £, £ } ⊆ G( £ ). Since G( £ ) Å {d £ / i(mod n)É0 ° i õ d}, n õ d. W: Networks 743 44 HASUNUMA AND SHIBATA Now, we prove the main theorem of this paper. In the theorem and the following corollary, we use the Möbius function. The Möbius function m is defined as follows: 1 m(d) Å Fig. 5. if d is a product of an even number of distinct primes, if d is a product of an odd number of distinct primes, otherwise. 01 0 Let d ° n õ d 2 . From Lemma 4.1, u(GB (n, d)) ° 3. Since d ° n, u(GB (n, d)) ú 2. Hence, u(GB (n, d)) Å 3. Conversely, let u(GB (n, d)) Å 3. Then, d ° n. Hence, there are no multiarcs in GB (n, d), which follows a similar consideration to the case of multiloops. Thus, u(GB (n, d)) Å 3 means that GB (n, d) contains a subdigraph isomorphic to the digraph in Figure 5. Suppose that GB (n, d) has the subgraph shown in Figure 5. Let di å i 0 m(mod n) and j 0 i å k(mod n). Suppose that k ° d 0 m 0 1. Then, G(i) Å {i 0 m, . . . , i, . . . , j, . . . , i / d 0 m 0 1}, Theorem 4.5. Let n Å pd h , where d É/ p, and gl Å gcd(d l 0 1, n). If p õ d 3 and k ° logd n / 1, or p ú d 3 and k ° h / 3, then the number of cycles of length k in GB (n, d) is given by SD k 1 gl ∑m k l Ék l dl gl , where m is the Möbius function. Proof. Let C(k) be the number of cycles of length k in GB (n, d). From Lemma 4.4, G(i / 1) Å {i / d 0 m, . . . , i / 2d 0 m 0 1}, G(i / 2) Å {i / 2d 0 m, . . . , i / 3d 0 m 0 1}, : GB (pd h , d) à L h (GB (p, d)). G( j) Å {i / kd 0 m, . . . , i / (k / 1)d 0 m 0 1}, where all numbers are modulo n. Since i √ G( j), n ° É{i / 1, . . . , i / (k / 1)d 0 m 0 1}É. Thus, n ° (k / 1)d 0 m 0 1. Then, n ° d 2 0 1 because 0 ° m õ d and 0 õ k õ d. For the case k ú d 0 m 0 1, we can similarly prove that n õ d 2 . j Then, we count the number of nonperiodic closed walks of length k in GB (p, d) and use Theorem 3.5. Let Xk (GB (p, d)) be the set of nonperiodic closed walks of length k in GB (p, d). Let N(k) be the number of nonperiodic closed walks of length k in GB (p, d). Then, In Shibata et al. [13], the cardinality of the set of closed walks in generalized de Bruijn digraphs has been counted. Lemma 4.3 [13]. Let gk Å gcd(d k 0 1, n). Then, the cardinality of the set of closed walks of length k in GB (n, d) is gk d k /gk . The next relation between generalized de Bruijn digraphs and the line digraph operation was shown by Imase et al. [7]. É Xk (GB (p, d))É . k A periodic closed walk of length k consists of several iterations of a nonperiodic closed walk whose length is a divisor of k. Hence, the cardinality of the set of closed walks of length k in GB (p, d) can be represented by (l ÉkÉ Xl (GB (p, d))É. Since gcd(d k 0 1, d) Å 1, gcd(d k 0 1, p) Å gcd(d k 0 1, n) Å gk . Therefore, from Lemma 4.3, we have dk gk ∑ lN(l) Å ∑ É Xl (GB (p, d))É Å gk Lemma 4.4 [7]. l Ék GB (nd, d) à L(GB (n, d)). 11-15-96 17:06:07 l Ék Using the Möbius inversion formula (see [14]), Mora et al. [10] studied the c-circulant digraph which is a generalization of the generalized de Bruijn digraph. Then, they showed a general version of Lemma 4.4. / 8u0d$$0005 N(k) Å netwa kN(k) Å ∑ m(l)gk /l l Ék W: Networks 743 d k/l gk /l . . COUNTING SMALL CYCLES IN DE BRUIJN DIGRAPHS 45 Replacing l by k/l, we get the following formula: N(k) Å SD 1 k gl ∑m k l Ék l gl l d gl . dl gl Å gl dl 0 1 / 1 gl Å gl From Theorem 3.5, if h ¢ k 0 u(GB (p, d)) / 1, then the number of cycles of length k in GB (n, d) equals to the number of nonperiodic closed walks of length k in GB (p, d), i.e., C(k) Å N(k). From Lemma 4.2, if p õ d 2 , then u(GB (p, d)) Å logd p / 2. Also, if p ú d 2 , then u(GB (p, d)) ¢ 4. Thus, if p õ d 2 and k ° logd n / 1, or p ú d 2 and k ° h / 3, then C(k) Å N(k). If d 2 õ p õ d 3 , then k ° h / 3 is equivalent to k ° logd n / 1. Therefore, if p õ d 3 and k ° logd n / 1, or p ú d 3 and k ° h / 3, then C(k) Å N(k). j In the case n Å d D , Theorem 4.5 gives the number of cycles of length k in a de Bruijn digraph B(d, D) where k ° D / 1. This number was shown by Mendelsohn [9]. For k Å 1, 2, and 3, we get the formula of the number of cycles of length k. When k Å 1, the formula gives the number of loops in generalized de Bruijn digraphs which has been shown by Du and Hwang [3]. Corollary 4.6. For k Å 1, 2 and 3, if n ¢ d k0 1 , then the number of cycles of length k in GB (n, d) is given by SD k 1 gl ∑m k l Ék l dl gl . In the following corollary, the ranges of the numbers of cycles of length k Å 1, 2, and 3 are shown. For N(1), the range has been shown in [3]. Corollary 4.7. Let N(k) be the number of cycles of length of k in GB (n, d). Then, • 2 d/1 3 SD ° N(3) ° 4 S D d/1 3 if n ¢ d 2 , Proof. We can rewrite the formula in Theorem 4.5 as SD 1 k (d l 0 1 / gl ), ∑m k l Ék l D Å d l 0 1 / gl . Here, 1 ° g1 Å gcd(d 0 1, n) ° d 0 1, 0 ° g2 0 g1 Å gcd((d 0 1)(d / 1), n) 0 gcd(d 0 1, n) ° gcd(d 0 1, n)(gcd(d / 1, n) 0 1) ° (d 0 1)d and 0 ° g3 0 g1 Å gcd((d 0 1)(d 2 / d / 1), n) 0 gcd(d 0 1, n) ° gcd(d 0 1, n)(gcd(d 2 / d / 1, n) 0 1) ° (d 0 1) (d 2 / d). If gcd(d i 0 1, n) Å 1, then gi Å 1. Therefore, N(i) takes the minimum value when gcd(d i 0 1, n) Å 1. If (d i 0 1)Én, then gi Å d i 0 1. Therefore, N(i) takes the maximum value when (d i 0 1)Én. j In the following corollary, we use the Euler function w. Let d be a positive integer. Then, w(d) is the number of integers k with 1 ° k ° d such that gcd(d, k) Å 1. There is the following relation between the Möbius function and the Euler function: ∑ dÉn m(d) . d Corollary 4.8. Let n Å pd h , where d É/ p, and gl Å gcd(d l 0 1, n). If p õ d 3 and k ° logd n / 1, or p ú d 3 and k ° h / 3, then the number of cycles whose length are divisors of k in GB (n, d) is given by SD k 1 gl ∑w k l Ék l dl gl , where w is the Euler function. Proof. Let D(k) be the number of cycles whose length are divisors of k in GB (n, d). Then, because of the following derivation: 11-15-96 17:06:07 1 gl • N(1) Å d 0 1 / g1 , 1 • N(2) Å ((d 2 0 1 / g2 ) 0 (d 0 1 / g1 )) 2 1 d(d 0 1) Å (g2 0 g1 ) / , if n ¢ d, 2 2 1 • N(3) Å ((d 3 0 1 / g3 ) 0 (d 0 1 / g1 )) 3 1 (d / 1)d(d 0 1) Å (g3 0 g1 ) / , if n ¢ d 2 . 3 3 w(n) Å n such that N(i), 1 ° i ° 3, takes the minimum value when gcd(d i 0 1, n) Å 1 and the maximum value when (d i 0 1)Én. / 8u0d$$0005 dl 0 1 / gl Since m(1) Å 1, m(2) Å 01, and m(3) Å 01, • d ° N(1) ° 2(d 0 1), d d • ° N(2) ° 2 if n ¢ d, 2 2 SD S D S netwa W: Networks 743 46 HASUNUMA AND SHIBATA D(k) Å ∑ C(m) m Ék Å ∑ m Ék Å ∑ l Ém ,m Ék Å Å Å dl gl 1 l dl gl 1 l dl gl ∑ gl ∑ gl l Ék SD dl gl 1 m(p)gl pl ∑ l Ék dl gl 1 m m gl m l l Ék ,p Ék /l Å SD 1 m gl ∑m m l Ém l SD 1 k gl ∑w k l Ék l ∑ p Ék /l m(p) p Fig. 7. SD l k w k l dl gl . j For any k, D(k) is also the number of closed walks of length k in GB (n, d). The number was shown in [13]. 5. CONCLUDING REMARKS In this paper, we counted the number of small cycles in generalized de Bruijn digraphs. The methods of counting of loops in [3] and closed walks in [13] are based on number theory. The method of our counting is based on a property of the line digraph operation, i.e., for any nonperiodic closed walk of length k in G, the nonperiodic closed walk corresponds to a cycle in L m (G) for any nonnegative integer m ¢ k 0 u(G) / 1. If u(GB (p, d)) Å logd p / 2, then the number of cycles of length k ° logd n / 1 in GB (pd h , d) is determined applying the consideration in this paper. From Lemma 4.1, the upper bound of length of cycles countable with our method is logd n / 1. Lemma 4.2 shows that if p õ d 3 then u(GB (p, d)) Å logd p / 2. The equation does not hold in general. For example, u(GB (9, 2)) Å 4 because GB (9, 2) (Fig. 6) contains a subdigraph isomorphic to the digraph in Figure 7. Thus, we cannot extend Corollary 4.6 for k Å 4. For long cycles in generalized de Bruijn digraphs, the existence of Hamiltonian cycles was characterized by Du et al. [2, 3]. Also, if dÉn, then the number of Hamiltonian cycles in GB (n, d) was determined by Li and Zhang [8]. The authors are very thankful to the anonymous referees for their valuable comments and suggestions that improved the style of the paper and the proof of Theorem 3.5. REFERENCES [1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] Fig. 6. GB (9, 2). / 8u0d$$0005 11-15-96 17:06:07 netwa J.-C. Bermond and C. Peyrat, De Bruijn and Kautz networks: A competitor for the hypercube? Hypercube and Distributed Computers. (F. André and J. P. Verjus, Eds.). Elsevier North-Holland, Amsterdam (1989). D. Z. Du, D. F. Hsu, F. K. Hwang, and X. M. Zhang, The Hamiltonian property of generalized de Bruijn digraphs. J. Combin. Theory Ser. B 52 (1991) 1–8. D. Z. Du and F. K. Hwang, Generalized de Bruijn digraphs. Networks 18 (1988) 27–38. S. W. Golomb, Shift Register Sequence. Aegean Park Press, Laguna Hills, CA (1982). R. L. Hemminger and L. W. Beineke, Line graphs and line digraphs. Selected Topics in Graph Theory. Academic Press, New York (1983) 271–305. M. Imase and M. Itoh, Design to minimize diameter on building-block network. IEEE Trans. Comput. C-30 (1981) 439–442. M. Imase, T. Soneoka, and K. Okada, Connectivity of regular directed graphs with small diameters. IEEE Trans. Comput. C-34 (1985) 267–273. W: Networks 743 COUNTING SMALL CYCLES IN DE BRUIJN DIGRAPHS [ 8] X. Li and F. Zhang, On the numbers of spanning trees and Eulerian tours in generalized de Bruijn graphs. Discr. Math. 94 (1991) 189–197. [ 9] N. S. Mendelsohn, Directed graphs with the unique path property. Combinatorial Theory and Its Applications II (Proc. Colloq. Balatonfürer, 1969), North-Holland, Amsterdam (1970) 783–799. [10] M. Mora, O. Serra, and M. A. Fiol, General properties of c-circulant digraphs. Ars Combin. 25C (1988) 241– 252. [11] S. M. Reddy, D. K. Pradhan, and J. G. Kuhl, Direct graphs with minimum diameter and maximal connectiv- / 8u0d$$0005 11-15-96 17:06:07 netwa [12] [13] [14] 47 ity. School of Engineering, Oakland University Technical Report (July 1980). R. A. Rowley and B. Bose, Fault-tolerant ring embedding in de Bruijn networks. IEEE Trans. Comput. C-42 (1993) 1480–1486. Y. Shibata, M. Shirahata, and S. Osawa, Counting closed walks in generalized de Bruijn graphs. Info. Process. Lett. 49 (1994) 135–138. J. H. van Lint and R. M. Wilson, A Course in Combinatorics. Cambridge University Press, Cambridge (1992). Received November 30, 1993 Accepted June 27, 1996 W: Networks 743

1/--страниц