Kautz graph

The Kautz graph ${\displaystyle K_{M}^{N+1}}$ is a directed graph of degree ${\displaystyle M}$ and dimension ${\displaystyle N+1}$, which has ${\displaystyle (M+1)M^{N}}$ vertices labeled by all possible strings ${\displaystyle s_{0}\cdots s_{N}}$ of length ${\displaystyle N+1}$ which are composed of characters ${\displaystyle s_{i}}$ chosen from an alphabet ${\displaystyle A}$ containing ${\displaystyle M+1}$ distinct symbols, subject to the condition that adjacent characters in the string cannot be equal (${\displaystyle s_{i}\neq s_{i+1}}$).

Example of Kautz graph on 3 characters with string length 2 (on the left) and 3 (on the right); the edges on the left correspond to the vertices on the right.

The Kautz graph ${\displaystyle K_{M}^{N+1}}$ has ${\displaystyle (M+1)M^{N+1}}$ edges

${\displaystyle \{(s_{0}s_{1}\cdots s_{N},s_{1}s_{2}\cdots s_{N}s_{N+1})|\;s_{i}\in A\;s_{i}\neq s_{i+1}\}\,}$

It is natural to label each such edge of ${\displaystyle K_{M}^{N+1}}$ as ${\displaystyle s_{0}s_{1}\cdots s_{N+1}}$, giving a one-to-one correspondence between edges of the Kautz graph ${\displaystyle K_{M}^{N+1}}$ and vertices of the Kautz graph ${\displaystyle K_{M}^{N+2}}$.

Kautz graphs are closely related to De Bruijn graphs.