Kautz graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 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.

Properties[edit]

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

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

  1. ^ Darcy, Jeff (2007-12-31). "The Kautz Graph". Canned Platypus. 
  2. ^ Li, Dongsheng; Xicheng Lu; Jinshu Su (2004). "Network and Parallel Computing: IFIP International Conference". Wuhan, China: NPC. pp. 308–315. ISBN 3-540-23388-1. Retrieved 2008-03-05.  |chapter= ignored (help)

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