The Cayley Digraph Associated to the Kautz Digraph

Abstract

De Bruijn digraphs and shuffle-exchange graphs are useful models for interconnection networks. They can be represented as group action graphs of the wrapped butterfly graph and the cube-connected cycles, respectively. The Kautz digraph has similar definitions and properties to de Bruijn digraphs. It is $d$-regular and strongly $d$-connected, thus it is a group action graph. In this paper, we use another representation of the Kautz digraph and settle the open problem posed by M.-C. Heydemann in $[6]$.