A family of efficient six-regular circulants representable as a Kronecker product

详细信息    查看全文

• 作者：Pranava K. Jha ^{pkjha384@hotmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Six-regular circulants ; Kronecker product ; Mö ; bius ladder ; Twisted torus ; Network topology ; Routing ; Embedding ; Graphs and networks
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 April 2016
• 年：2016
• 卷：203
• 期：Complete
• 页码：72-84
• 全文大小：1243 K

文摘

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 Möbius ladder and an odd cycle. The order of each graph is equal to 4d²−2d−2$4d^2-2d-2$ where 478c111148d9a8692deb7d724e" title="Click to view the MathML source">d$d$ denotes the diameter and d≡3,5$d\equiv 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 478c111148d9a8692deb7d724e" title="Click to view the MathML source">d$d$ and order 3d²+3d+1$3d^2+3d+1$.