Kautz graph explained

The Kautz graph

K ^{N +1} _{M} is a directed graph of degree M and dimension N + 1 , which has (M +1 )M ^{N} vertices labeled by allpossible strings s _{0} … s _{N} of length N + 1 which are composed of characters s _{i} chosen froman alphabet A containing M + 1 distinctsymbols, subject to the condition that adjacent characters in thestring cannot be equal (s _{i} ≠ s _{i+} ).

The Kautz graph

K ^{N +1} _{M} has (M + 1 )M ^{N +} edges\{(s _{0} s _{1} … s _{N,s} _{1} s _{2} … s _{N} s _{N} )| s _{i} \in A s _{i} ≠ s _{i} \}

It is natural to label each such edge of

K ^{N +1} _{M} as s _{0s} _{1} … s _{N} , giving a one-to-one correspondencebetween edges of the Kautz graph K ^{N +1} _{M} and vertices of the Kautz graphK ^{N +2} _{M} .

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 ^{N} _{M} and vertices of the Kautz graph K ^{N +1} _{M} ; a Hamiltonian cycle on K ^{N +1} _{M} is given by an Eulerian cycle on K ^{N} _{M} )

• 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 and fault-tolerant computing^[1] applications: such a network is known as a Kautz network.

Notes and References

1. Dongsheng . Li . Xicheng Lu . Jinshu Su . Graph-Theoretic Analysis of Kautz Topology and DHT Schemes . Network and Parallel Computing: IFIP International Conference . 308–315 . NPC . 2004 . Wuhan, China . 2008-03-05 . 3-540-23388-1 .