On extremal factors of de Bruijn-like graphs

Abstract

In 1972, Mykkeltveit confirmed Golomb’s conjecture on the de Bruijn graphs: he proved that the pure cycling register rule yields the maximum number of vertex-disjoint cycles in de Bruijn graphs. We show that this result encompasses the tensor product of the de Bruijn graph for strings of length n with a simple cycle of size k, when n divides k or vice versa. Furthermore, we give counting formulas for an array of cycling register rules, which includes Golomb’s well-studied linear register rules.