Geodesic
Generalized de Bruijn graphs
Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 52-88

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the graphs of transitions between states of nonautonomous automata that provide, with independent equiprobable input signs, an equiprobable distribution on the set of all states in the minimum possible number of cycles, as is the case of the de Bruijn graphs corresponding to shift registers. It is proved that in the case of a binary input alphabet, there are at least $12r-33$ pairwise nonisomorphic directed graphs with $2^r$ vertices that have this property. All graphs of this type with 8 and 9 vertices are found.
Keywords: de Bruijn graphs, dual graphs, isomorphisms of graphs, generalized de Bruijn graphs. 
@article{DM_2020_32_4_a3,
     author = {F. M. Malyshev},
     title = {Generalized de {Bruijn} graphs},
     journal = {Diskretnaya Matematika},
     pages = {52--88},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2020_32_4_a3/}
}
TY  - JOUR
AU  - F. M. Malyshev
TI  - Generalized de Bruijn graphs
JO  - Diskretnaya Matematika
PY  - 2020
SP  - 52
EP  - 88
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2020_32_4_a3/
LA  - ru
ID  - DM_2020_32_4_a3
ER  - 
%0 Journal Article
%A F. M. Malyshev
%T Generalized de Bruijn graphs
%J Diskretnaya Matematika
%D 2020
%P 52-88
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2020_32_4_a3/
%G ru
%F DM_2020_32_4_a3
F. M. Malyshev. Generalized de Bruijn graphs. Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 52-88. http://geodesic.mathdoc.fr/item/DM_2020_32_4_a3/