Kautz Graph

The Kautz graph $K_M^$ is a
directed graph of degree $M$ and dimension $N+ 1$, which has $(M +1)M^$ 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_$).

The Kautz graph $K_M^$ has $(M + 1)M^$ edges

$\ \,$

It is natural to label each such edge of $K_M^$
as $s_0s_1 \cdots s_$, giving a one-to-one correspondence
between edges of the Kautz graph $K_M^$
and vertices of the Kautz graph
$K_M^$.

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^$ and vertices of the Kautz graph $K_M^$; a Hamiltonian cycle on $K_M^$ is given by an Eulerian cycle on $K_M^$)
* 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

{{DEFAULTSORT:Kautz Graph
Parametric families of graphs
Directed graphs