Premium
Counting small cycles in generalized de Bruijn digraphs
Author(s) -
Hasunuma Toru,
Shibata Yukio
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199701)29:1<39::aid-net4>3.0.co;2-d
Subject(s) - de bruijn sequence , digraph , combinatorics , integer (computer science) , de bruijn graph , mathematics , function (biology) , discrete mathematics , computer science , evolutionary biology , biology , programming language
In this paper, we count small cycles in generalized de Bruijn digraphs. Let n = pd h , where d ??? p , and g l = gcd ( d 1 ‐ 1, n ). We show that if p < d 3 and k ≤ ⌊log d n ⌋ + 1, or p > d 3 and k ≤ 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 Σ l/ k μ( k/l ) g l ⌈ d 1 / g l ⌉, where μ is the Möbius function and ⌈ r ⌉ denotes the smallest integer not smaller than a real number r . © 1997 John Wiley & Sons, Inc.