Kautz graph

Sample of K. graph with M=2: on the left N=1, on the right N=2. The edges of the left graph correspond to the nodes of right graph. Note that the graph on the right is missing three edges.

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

Notes

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