Kautz graph
The Kautz graph is a
directed graph of degree and dimension, which has vertices labeled by all
possible strings of length which are composed of characters chosen from
an alphabet containing distinct
symbols, subject to the condition that adjacent characters in the
string cannot be equal.
The Kautz graph has 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.Properties
- For a fixed degree and number of vertices, the Kautz graph has the smallest diameter of any possible directed graph with vertices and degree.
- All Kautz graphs have Eulerian cycles.
- All Kautz graphs have a Hamiltonian cycle
- A degree- Kautz graph has disjoint paths from any node to any other node.
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.
