COUNTING SMALL CYCLES IN GENERALIZED DE-BRUIJN DIGRAPHS

In this paper, we count small cycles in generalized de Bruijn digraphs . Let n = pd(h), where d inverted iota p, and g(l) = gcd(d(l) 1, n). W e show that if p < d(3) and k less than or equal to right perpendicula r log(d) n left perpendicular + 1, or p > d(3) and k less than or equa l to h + 3, then the number of cycles of length k in a generalized de Bruijn digraph G(B)(n, d) is given by 1/k Sigma(l/k)mu(k/l)g(i) invert ed right perpendicular d(l)/g(i) inverted left perpendicular, where mu is the Mobius function and inverted right perpendicular r inverted le ft perpendicular denotes the smallest integer not smaller than a real number r. (C) 1997 John Wiley & Sons, Inc.