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

The Kautz graph ${\cal K}_{K}^{{N+1}}$ has $(K+1)K^{{N+1}}$ edges

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

Example:

The Kautz graph ${\cal K}_{2}^{{2}}$ has 6 nodes, and is depicted in the following figure (using the alphabet $A$ ={0, 1, 2})

Properties:

$\bullet$ The diameter of the Kautz graph ${\cal K}_{K}^{{N}}$ is $N$
(For example, there is a path of length $N$ from $x$ to $y$ achieved by the sequence of edges $(x_{0}x_{1}\cdots x_{N},x_{1}\cdots x_{N}y_{0})$, …$(x_{N}y_{0}\cdots y_{{N-1}},y_{0}\cdots y_{N})$ unless $x_{N}=y_{0}$ in which case there is a similar path of length $N-1$ beginning $(x_{0}x_{1}\cdots x_{{N-1}}y_{0},x_{1}\cdots x_{{N-1}}y_{0}y_{1}),\ldots$.)

$\bullet$ Kautz graphs are closely related to de Bruijn graphs, which are defined similarly but without the condition $s_{i}\neq s_{{i+1}}$, and with an alphabet of only $K$ symbols for the degree $K$ de Bruijn graph.

$\bullet$ For a fixed degree $K$ and number of vertices $V=(K+1)K^{N}$, the Kautz graph has the smallest diameter of any possible directed graph with $V$ vertices and degree $K$.

$\bullet$ All Kautz graphs have Eulerian cycles
(An Eulerian cycle is one which visits each edge exactly once– This result follows because Kautz graphs have in-degree equal to out-degree for each node)

$\bullet$ All Kautz graphs have a Hamiltonian cycle
(This result follows from the correspondence described above between edges of the Kautz graph ${\cal K}_{K}^{{N}}$ and vertices of the Kautz graph ${\cal K}_{K}^{{N+1}}$; a Hamiltonian cycle on ${\cal K}_{K}^{{N+1}}$ is given by an Eulerian cycle on ${\cal K}_{K}^{{N}}$)

$\bullet$ A degree-$k$ Kautz graph has $k$ disjoint paths from any node $x$ to any other node $y$.