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 ().

Example of Kautz graph on 3 characters with string length 2 (on the left) and 3 (on the right); the edges on the left correspond to the vertices on the right.

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

edit
  • 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. (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-  Kautz graph has   disjoint paths from any node   to any other node  .

In computing

edit

The Kautz graph has been used as a network topology for connecting processors in high-performance computing and fault-tolerant computing[1] applications: such a network is known as a Kautz network.

Notes

edit
  1. ^ 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.

This article incorporates material from Kautz graph on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.