On extremal factors of de Bruijn-like graphs

Authors: Nicolás Álvarez, Verónica Becher, Martín Mereb, Ivo Pajor, Carlos Miguel Soto.

Abstract:
In 1972 Mykkeltveit proved that the maximum number of vertex-disjoint cycles in the de Bruijn graphs of order n is attained by the pure cycling register rule, as conjectured by Golomb. We generalize this result to the tensor product of the de Bruijn graph of order n and a simple cycle of size k, when n divides k or vice versa. We also develop counting formulae for a large family of cycling register rules, including the linear register rules proposed by Golomb.

More information:
https://arxiv.org/abs/2308.16257