Kautz graph

The Kautz graph 𝒦KN+1 is a digraphMathworldPlanetmath (directed graph) of degree K and dimension N+1, which has (K+1)⁒KN vertices labeled by all possible strings s0⁒⋯⁒sN of length N+1 which are composed of characters si chosen from an alphabet A containing K+1 distinct symbols, subject to the condition that adjacent characters in the string cannot be equal (siβ‰ si+1).

The Kautz graph 𝒦KN+1 has (K+1)⁒KN+1 edges

{(s0⁒s1⁒⋯⁒sN,s1⁒s2⁒⋯⁒sN⁒sN+1)|si∈A⁒siβ‰ si+1}. (1)

It is natural to label each such edge of 𝒦KN+1 as s0⁒s1⁒⋯⁒sN+1, giving a one-to-one correspondence between edges of the Kautz graph 𝒦KN+1 and vertices of the Kautz graph 𝒦KN+2.


The Kautz graph 𝒦22 has 6 nodes, and is depicted in the following figure (using the alphabet A ={0, 1, 2})

βˆ™ The diameter of the Kautz graph 𝒦KN is N
(For example, there is a path of length N from x to y achieved by the sequence of edges (x0⁒x1⁒⋯⁒xN,x1⁒⋯⁒xN⁒y0), …(xN⁒y0⁒⋯⁒yN-1,y0⁒⋯⁒yN) unless xN=y0 in which case there is a similar path of length N-1 beginning (x0⁒x1⁒⋯⁒xN-1⁒y0,x1⁒⋯⁒xN-1⁒y0⁒y1),….)

βˆ™ Kautz graphs are closely related to de Bruijn graphs, which are defined similarly but without the condition siβ‰ si+1, and with an alphabet of only K symbols for the degree K de Bruijn graph.

βˆ™ For a fixed degree K and number of vertices V=(K+1)⁒KN, the Kautz graph has the smallest diameter of any possible directed graph with V vertices and degree K.

βˆ™ 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 cycleMathworldPlanetmath
(This result follows from the correspondence described above between edges of the Kautz graph 𝒦KN and vertices of the Kautz graph 𝒦KN+1; a Hamiltonian cycle on 𝒦KN+1 is given by an Eulerian cycle on 𝒦KN)

βˆ™ A degree-k Kautz graph has k disjoint paths from any node x to any other node y.

Title Kautz graph
Canonical name KautzGraph
Date of creation 2013-03-22 16:22:55
Last modified on 2013-03-22 16:22:55
Owner wati (15191)
Last modified by wati (15191)
Numerical id 7
Author wati (15191)
Entry type Definition
Classification msc 05C20
Related topic DeBruijnDigraph