On extremal factors of de Bruijn-like graphs

08/30/2023
by   Nicolás Álvarez, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset