Kautz graph

From Wikipedia, the free encyclopedia

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.

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.

[edit] 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$ .

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

[edit] Notes

^ Darcy, Jeff (2007-12-31). The Kautz Graph. Canned Platypus.
^ Li, Dongsheng; Xicheng Lu, Jinshu Su (2004). "Graph-Theoretic Analysis of Kautz Topology and DHT Schemes". Network and Parallel Computing: IFIP International Conference: 308-315, Wuhan, China: NPC. Retrieved on 2008-03-05.