Kautz graph

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 {\displaystyle K_{M}^{N+1}} is a directed graph of degree M {\displaystyle M} and dimension N + 1 {\displaystyle N+1} , which has ( M + 1 ) M N {\displaystyle (M+1)M^{N}} vertices labeled by all possible strings s 0 ⋯ s N {\displaystyle s_{0}\cdots s_{N}} of length N + 1 {\displaystyle N+1} which are composed of characters s i {\displaystyle s_{i}} chosen from an alphabet A {\displaystyle A} containing M + 1 {\displaystyle M+1} distinct symbols, subject to the condition that adjacent characters in the string cannot be equal ( s i ≠ s i + 1 {\displaystyle s_{i}\neq s_{i+1}} ).

The Kautz graph K M N + 1 {\displaystyle K_{M}^{N+1}} has ( M + 1 ) M N + 1 {\displaystyle (M+1)M^{N+1}} edges

{ ( s 0 s 1 ⋯ s N , s 1 s 2 ⋯ s N s N + 1 ) | s i ∈ A s i ≠ s i + 1 } {\displaystyle \{(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 {\displaystyle K_{M}^{N+1}} as s 0 s 1 ⋯ s N + 1 {\displaystyle s_{0}s_{1}\cdots s_{N+1}} , giving a one-to-one correspondence between edges of the Kautz graph K M N + 1 {\displaystyle K_{M}^{N+1}} and vertices of the Kautz graph K M N + 2 {\displaystyle K_{M}^{N+2}} .

Kautz graphs are closely related to De Bruijn graphs.

Properties

  • For a fixed degree M {\displaystyle M} and number of vertices V = ( M + 1 ) M N {\displaystyle V=(M+1)M^{N}} , the Kautz graph has the smallest diameter of any possible directed graph with V {\displaystyle V} vertices and degree M {\displaystyle 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 {\displaystyle K_{M}^{N}} and vertices of the Kautz graph K M N + 1 {\displaystyle K_{M}^{N+1}} ; a Hamiltonian cycle on K M N + 1 {\displaystyle K_{M}^{N+1}} is given by an Eulerian cycle on K M N {\displaystyle K_{M}^{N}} )
  • A degree- k {\displaystyle k} Kautz graph has k {\displaystyle k} disjoint paths from any node x {\displaystyle x} to any other node y {\displaystyle y} .

In computing

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

  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.