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_{0}s_{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.
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.
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.
Notes
Darcy, Jeff (2007-12-31). "The Kautz Graph". Canned Platypus. External link in |publisher= (help)
Li, Dongsheng; Xicheng Lu; Jinshu Su (2004). "Graph-Theoretic Analysis of Kautz Topology and DHT Schemes". Network and Parallel Computing: IFIP International Conference. Wuhan, China: NPC. pp. 308–315. ISBN 3-540-23388-1. Retrieved 2008-03-05.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
