Kautz graph

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} \dots 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} \dots s_{N}, s_{1} s_{2} \dots 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} \dots 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.

Notes

↑ 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.

This article incorporates material from Kautz graph on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

[1] 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.