Back to Search
Start Over
A family of efficient six-regular circulants representable as a Kronecker product
- Source :
- Discrete Applied Mathematics. 203:72-84
- Publication Year :
- 2016
- Publisher :
- Elsevier BV, 2016.
-
Abstract
- Broere and Hattingh proved that the Kronecker product of two circulants whose orders are co-prime is a circulant itself. This paper builds on this result to construct a family of efficient three-colorable, six-regular circulants representable as the Kronecker product of a Mobius ladder and an odd cycle. The order of each graph is equal to 4 d 2 - 2 d - 2 where d denotes the diameter and d ? 3 , 5 (mod 6). Additional results include (a) distance-wise vertex distribution of the circulant leading to its average distance that is about two-thirds of the diameter, (b) routing via shortest paths, and (c) an embedding of the circulant on a torus with a half twist. In terms of the order-diameter ratio and odd girth, the circulants in this paper surpass the well-known triple-loop networks having diameter d and order 3 d 2 + 3 d + 1 .
- Subjects :
- Kronecker product
Discrete mathematics
Applied Mathematics
010102 general mathematics
Torus
Möbius ladder
0102 computer and information sciences
01 natural sciences
Graph
Combinatorics
symbols.namesake
010201 computation theory & mathematics
symbols
Discrete Mathematics and Combinatorics
Embedding
0101 mathematics
Twist
Circulant matrix
Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 203
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi...........a081a1c3eee377aa876a6ca657dc3b20