Kautz graph
From Wikipedia, the free encyclopedia
The Kautz graph 
is a directed graph of degree M and dimension N + 1, which has (M + 1)MN vertices labeled by all possible strings 
of length N + 1 which are composed of characters si chosen from an alphabet A containing M + 1 distinct symbols, subject to the condition that adjacent characters in the string cannot be equal (
).
The Kautz graph has (M + 1)MN + 1 edges
It is natural to label each such edge of as 
, giving a one-to-one correspondence between edges of the Kautz graph and vertices of the Kautz graph 
.
Kautz graphs are closely related to De Bruijn graphs.
[edit] Properties
- For a fixed degree M and number of vertices V = (M + 1)MN, 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
and vertices of the Kautz graph ; a Hamiltonian cycle on is given by an Eulerian cycle on )
- 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 and fault-tolerant computing applications: such a network is known as a Kautz network.
This article incorporates material from Kautz graph on PlanetMath, which is licensed under the GFDL.
