Isomorphic factorization, the Kronecker product and the line digraph. (English) Zbl 1185.05118
Summary: We investigate isomorphic factorizations of the Kronecker product graphs. Using these relations, it is shown that (1) the Kronecker product of the \(d\)-out-regular digraph and the complete symmetric digraph is factorized into the line digraph, (2) the Kronecker product of the Kautz digraph and the de Bruijn digraph is factorized into the Kautz digraph, (3) the Kronecker product of binary generalized de Bruijn digraphs is factorized into the binary generalized de Bruijn digraph.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68M10 | Network design and communication in computer systems |
Keywords:
interconnection network; isomorphic factorization; Kronecker product; line digraph; Kautz digraph; binary generalized de Bruijn digraphReferences:
| [1] | Bermond, J.-C.; Darrot, E.; Delmas, O.; Perennes, S., Hamilton circuits in the directed wrapped Butterfly network, Discrete Math., 84, 21-42 (1998) · Zbl 0901.05062 |
| [2] | Bermond, J.-C.; Peyrat, C., De Bruijn and Kautz networks: a competitor for the hypercube?, (André, F.; Verjus, J. P., Hypercube and Distributed Computers (1989), North-Holland: North-Holland Amsterdam), 279-293 |
| [3] | Chartrand, G.; Lesniak, L., Graphs & Digraphs (2004), Chapman&Hall/CRC: Chapman&Hall/CRC London/Boca Raton, FL |
| [4] | Harary, F.; Robinson, R. W.; Wormald, N. C., Isomorphic factorisations I: Complete graphs, Trans. Amer. Math. Soc., 242, 243-260 (1978) · Zbl 0381.05044 |
| [5] | Harary, F.; Robinson, R. W.; Wormald, N. C., Isomorphic factorisations V: Directed graphs, Mathematika, 25, 279-285 (1978) · Zbl 0387.05015 |
| [6] | Harary, F.; Robinson, R. W., Isomorphic factorisations X: Unsolved problems, J. Graph Theory, 9, 67-86 (1985) · Zbl 0617.05051 |
| [7] | Imase, M.; Soneoka, T.; Okada, K., Connectivity of regular directed graphs with small diameters, IEEE Trans. Comput. C-34, 267-273 (1985) · Zbl 0554.05044 |
| [8] | Shibata, Y.; Hasunuma, T.; Fukuda, S., Isomorphic factorization of de Bruijn digraphs, Discrete Math., 218, 199-208 (2000) · Zbl 0951.05082 |
| [9] | Shibata, Y.; Gonda, Y., Extension of de Bruijn and Kautz graph, Comput. Math. Appl., 30, 51-61 (1995) · Zbl 0835.68090 |
| [10] | Y. Tanaka, Y. Shibata, The Cayley digraph associated to the Kautz digraph, submitted for publication; Y. Tanaka, Y. Shibata, The Cayley digraph associated to the Kautz digraph, submitted for publication · Zbl 1240.05150 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
