Generalized de Bruijn graphs

Oriented graphs in which every pair of vertices can be connected by a unique path of given length (not depending on the choice of the pair of vertices) are studied. These graphs are a natural extension of the well-known de Bruijn graphs and retain their most important properties. Some results on the structure of and methods for constructing such graphs are obtained. Translated fromMatematicheskie Zametki, Vol. 62, No. 4, pp. 540–548, October, 1997. Translated by O. V. Sipacheva