Generalized de Bruijn graphs

F. M. Malyshev

Diskretnaya Matematika, Tome 32 (2020) no. 4, pp. 52-88.

Résumé

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.

Détail

Keywords: de Bruijn graphs, dual graphs, isomorphisms of graphs, generalized de Bruijn graphs.

Bibliographie

[1] De Bruijn N.G., “A combinatorial problem”, Proc. Sect. Sci. Koninkl. Nederl. Akad. Wetensch. Amsterdam, 49:7 (1946), 758–764 | MR

[2] Kholl M., Kombinatorika, Mir, M., 1970, 424 pp. | MR

[3] Good I.J., “Normal recurring decimals”, J. London Math. Soc., 21:3 (1946), 167–169 | DOI | MR | Zbl

[4] Fredricksen H., “A survey of full length nonlinear shift register cycle algorithms”, SIAM Rev., 24:2 (1982), 195–221 | DOI | MR | Zbl

[5] Kratko M.I., Strok V.V., “Posledovatelnosti de Breina s ogranicheniyami”, Voprosy kibernetiki. Kombinatornyi analiz i teoriya grafov, Nauka, M., 1980, 80–84

[6] Sherisheva E.V., “O chisle konechnykh avtomatov, ustanavlivaemykh postoyannym vkhodom v fiksirovannoe sostoyanie”, Diskretnaya matematika, 6:4 (1994), 80–86 | MR | Zbl

[7] Erokhin A. V., Malyshev F. M., Trishin A. E., “Mnogomernyi lineinyi metod i pokazateli rasseivaniya lineinoi sredy shifrpreobrazovanii”, Matematicheskie voprosy kriptografii, 8:4 (2017), 29-62

[8] Kharari F., Teoriya grafov, Mir, M., 1973, 302 pp.; Harary F., Graph Theory, Addison-Wesley, 1969, 274 pp. | MR | Zbl

[9] Fisher P., Aljohani N., Baek J., “Generation of finite inductive, pseudo random, binary sequences”, J. Inf. Process. Syst., 13:6 (2017), 1554–1574

[10] Wu J., Jia R., Li Q., “$g$-circulant solutions to the (0,1)-matrix equation $A^m=J_n$”, Linear Algebra Appl., 345:1 (2002), 195–224 | MR | Zbl

[11] Hoffman A.J., “Research problem 2-11”, J. Combin. Theory, 2:3 (1967), 393 | DOI

[12] Trefois M., Van Dooren P., Delvenne J.-Ch., “Binary factorizations of the matrix of all ones”, Linear Alg. Appl., 468 (2015), 63–79 | DOI | MR | Zbl

[13] Ma S.L., Waterhouse W.C., “The g-circulant solutions of $A^m=\lambda J$”, Linear Algebra Appl., 85 (1987), 211–220 | DOI | MR | Zbl

[14] King F., Wang K., “On the g-circulant solutions to the matrix equation $A^m=\lambda J$”, J. Combin. Theory. Ser. A, 38:2 (1985), 182–186 | DOI | MR | Zbl

[15] Wang K., “On the $g$-circulant solutions to the matrix equation $A^m=\lambda J$”, J. Combin. Theory. Ser. A, 33:3 (1982), 287–296 | DOI | MR

[16] Wang T., Wang J., “On some solutions to the matrix Equation $A^m=J$”, J. Dalian Univ. Technology, 10:6 (1990), 621–624 | MR

[17] Du D.Z., Hwang F.K., “Generalized de Bruijn digraphs”, Networks, 18:1 (1988), 27–38 | DOI | MR | Zbl

[18] Esfahanian A.H., Hakimi S.L., “Faul-tolerant routing in de Bruin communication networks”, IEEE Trans. Comput., C-34:9 (1985), 777–788 | DOI | MR

[19] Pradhan D.K., “Fault-tolerant multiprocessor and VSLI-based systems communication architecture”, Fault Tolerant Computing Theory and Techniques, v. II, Prentice-Hall, Englewood Cliffs, NJ, 1986, 467–576

[20] Grodzki Z., Wronski A., “Generalized de Bruijn multigraphs of rank $\overrightarrow{k}$”, Ars Combinatoria, 50 (1998), 161–176 | MR | Zbl

[21] Malyshev F.M., Tarakanov V.E., “Obobschennye grafy de Breina”, Matematicheskie zametki, 62:4 (1997), 540–548 | Zbl

[22] Tarakanov V.E., “O gruppakh avtomorfizmov obobschennykh grafov de Breina”, Trudy po diskretnoi matematike, 5, FIZMATLIT, M., 235–240

[23] Malyshev F.M., “Beskonechnye serii prostykh obobschennykh grafov de Breina”, Algebra, teoriya chisel i diskretnaya geometriya: sovremennye problemy i prilozheniya, Mater. XV Mezhdunar. konf., TGPU im. L. N. Tolstogo, Tula, 2018, 187–190