Isomorphic factorization of de Bruijn digraphs (Q1978156): Difference between revisions

Let \(G\) be a directed graph. Define \(L^m(G)\) to be the digraph obtained from \(G\) by applying the line digraph operation \(m\) times. Furthermore, let \(K_d^+\) denote the complete digraph of order \(p\), that is, the digraph constructed from a complete symmetric digraph of order \(p\) by adding a loop to each vertex. The de Bruijn digraph \(B(d,D)\) is defined as \(B(d,D) = L^{D - 1}(K_d^+)\). In this paper, the authors show that a de Bruijn digraph \(B(d^k, D)\) has an isomorphic factorization into \(B(d, kD)\). They generalize this result to the Kronecker product of de Bruijn graphs (extended de Bruijn graphs).