close

Вход

Забыли?

вход по аккаунту

?

185

код для вставкиСкачать
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
Документ
Категория
Без категории
Просмотров
2
Размер файла
143 Кб
Теги
185
1/--страниц
Пожаловаться на содержимое документа