Cycle Kronecker products that are representable as optimal circulants

Broere and Hattingh proved that the Kronecker product of two cycles is a circulant if and only if the cycle lengths are coprime. In this paper, we specify which of these Kronecker products are actually optimal circulants. Further, we present their salient characteristics based on their edge decompositions into Hamiltonian cycles. It turns out that certain products thus distinguished have the added property of being tight-optimal, so their average distances are the least among all circulants of the same order and size. A benefit of the present study is that the existing results on the Kronecker product of two cycles may be used to good effect while putting these circulants into practice. The areas of applications include parallel computers, distributed systems and VLSI.