### - Art Gallery -

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[1] and fault-tolerant computing[2] applications: such a network is known as a Kautz network.
Notes

Darcy, Jeff (2007-12-31). "The Kautz Graph". Canned Platypus. External link in |publisher= (help)
Li, Dongsheng; Xicheng Lu; Jinshu Su (2004). "Graph-Theoretic Analysis of Kautz Topology and DHT Schemes". Network and Parallel Computing: IFIP International Conference. Wuhan, China: NPC. pp. 308–315. ISBN 3-540-23388-1. Retrieved 2008-03-05.