Kautz graph

The Kautz graph

+ 1

{\displaystyle K_{M}^{N+1}}

is a directed graph of degree

and dimension

+ 1

vertices labeled by all possible strings

of length

which are composed of characters

chosen from an alphabet

distinct symbols, subject to the condition that adjacent characters in the string cannot be equal (

The Kautz graph

edges

It is natural to label each such edge of

, 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.

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.

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

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.