Isomorphic factorization of de Bruijn digraphs (Q1978156)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Isomorphic factorization of de Bruijn digraphs |
scientific article |
Statements
Isomorphic factorization of de Bruijn digraphs (English)
0 references
11 December 2000
0 references
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).
0 references
isomorphic factorization
0 references
Kronecker product
0 references
line digraphs
0 references
de Bruijn digraphs
0 references
extended de Bruijn digraphs
0 references
interconnection networks
0 references
fault-tolerance
0 references