The Diameter of Cyclic Kautz Digraphs

Abstract

We present a new kind of digraphs, called cyclic Kautz digraphs $CK(d,\ell)$, which are subdigraphs of the well-known Kautz digraphs $K(d,\ell)$. The latter have the smallest diameter among all digraphs with their number of vertices and degree.

Cyclic Kautz digraphs $CK(d,\ell)$ have vertices labeled by all possible sequences $a_1\ldots a_\ell$ of length $\ell$, such that each character $a_i$ is chosen from an alphabet containing $d+1$ distinct symbols, where the consecutive characters in the sequence are different (as in Kautz digraphs), and now also requiring that $a_1\neq a_\ell$. Their arcs are between vertices $a_1
a_2\ldots a_\ell$ and $a_2 \ldots a_\ell a_{\ell+1}$, with $a_1\neq a_\ell$ and $a_2\neq a_{\ell+1}$.

We give the diameter of $CK(d,\ell)$ for all the values of $d$ and $\ell$, and also its number of vertices and arcs.