# Kautz graph 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 $K_{M}^{N+1}$ is a directed graph of degree $M$ and dimension $N+1$ , which has $(M+1)M^{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 $M+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 $K_{M}^{N+1}$ has $(M+1)M^{N+1}$ edges

$\{(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 $K_{M}^{N+1}$ as $s_{0}s_{1}\cdots s_{N+1}$ , giving a one-to-one correspondence between edges of the Kautz graph $K_{M}^{N+1}$ and vertices of the Kautz graph $K_{M}^{N+2}$ .

Kautz graphs are closely related to De Bruijn graphs.

## Properties

• For a fixed degree $M$ and number of vertices $V=(M+1)M^{N}$ , the Kautz graph has the smallest diameter of any possible directed graph with $V$ vertices and degree $M$ .
• 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)
• All Kautz graphs have a Hamiltonian cycle (This result follows from the correspondence described above between edges of the Kautz graph $K_{M}^{N}$ and vertices of the Kautz graph $K_{M}^{N+1}$ ; a Hamiltonian cycle on $K_{M}^{N+1}$ is given by an Eulerian cycle on $K_{M}^{N}$ )
• A degree-$k$ Kautz graph has $k$ disjoint paths from any node $x$ to any other node $y$ .

## In computing

The Kautz graph has been used as a network topology for connecting processors in high-performance computing and fault-tolerant computing applications: such a network is known as a Kautz network.