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 [math]\displaystyle{ K_M^{N + 1} }[/math] is a directed graph of degree [math]\displaystyle{ M }[/math] and dimension [math]\displaystyle{ N+ 1 }[/math], which has [math]\displaystyle{ (M +1)M^{N} }[/math] vertices labeled by all possible strings [math]\displaystyle{ s_0 \cdots s_N }[/math] of length [math]\displaystyle{ N + 1 }[/math] which are composed of characters [math]\displaystyle{ s_i }[/math] chosen from an alphabet [math]\displaystyle{ A }[/math] containing [math]\displaystyle{ M + 1 }[/math] distinct symbols, subject to the condition that adjacent characters in the string cannot be equal ([math]\displaystyle{ s_i \neq s_{i+ 1} }[/math]).

The Kautz graph [math]\displaystyle{ K_M^{N + 1} }[/math] has [math]\displaystyle{ (M + 1)M^{N + 1} }[/math] edges

[math]\displaystyle{ \{(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} \} \, }[/math]

It is natural to label each such edge of [math]\displaystyle{ K_M^{N + 1} }[/math] as [math]\displaystyle{ s_0s_1 \cdots s_{N + 1} }[/math], giving a one-to-one correspondence between edges of the Kautz graph [math]\displaystyle{ K_M^{N + 1} }[/math] and vertices of the Kautz graph [math]\displaystyle{ K_M^{N + 2} }[/math].

Kautz graphs are closely related to De Bruijn graphs.

Properties

• For a fixed degree [math]\displaystyle{ M }[/math] and number of vertices [math]\displaystyle{ V = (M + 1) M^N }[/math], the Kautz graph has the smallest diameter of any possible directed graph with [math]\displaystyle{ V }[/math] vertices and degree [math]\displaystyle{ M }[/math].
• 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 [math]\displaystyle{ K_M^{N} }[/math] and vertices of the Kautz graph [math]\displaystyle{ K_M^{N + 1} }[/math]; a Hamiltonian cycle on [math]\displaystyle{ K_M^{N + 1} }[/math] is given by an Eulerian cycle on [math]\displaystyle{ K_M^{N} }[/math])
• A degree-[math]\displaystyle{ k }[/math] Kautz graph has [math]\displaystyle{ k }[/math] disjoint paths from any node [math]\displaystyle{ x }[/math] to any other node [math]\displaystyle{ y }[/math].

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.