Kautz graph

The Kautz graph ${𝒦}_K^{N+1}$ is a digraph (directed graph) of degree $K$ and dimension $N+1$, which has $(K+1)K^N$ vertices labeled by all possible strings $s_0\mathrm{\cdots }{s}_N$ of length $N+1$ which are composed of characters $s_i$ chosen from an alphabet $A$ containing $K+1$ distinct symbols, subject to the condition that adjacent characters in the string cannot be equal ($s_i\ne s_{i+1}$).

The Kautz graph ${𝒦}_K^{N+1}$ has $(K+1)K^{N+1}$ edges

$$\{(s_0{s}_1\mathrm{\cdots }{s}_N,s_1{s}_2\mathrm{\cdots }{s}_N{s}_{N+1})|s_i\in A{s}_i\ne s_{i+1}\}.$$ (1)

It is natural to label each such edge of ${𝒦}_K^{N+1}$ as $s_0{s}_1\mathrm{\cdots }{s}_{N+1}$, giving a one-to-one correspondence between edges of the Kautz graph ${𝒦}_K^{N+1}$ and vertices of the Kautz graph ${𝒦}_K^{N+2}$.

Example:

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

Properties:

$\bullet$ The diameter of the Kautz graph ${𝒦}_K^N$ is $N$
(For example, there is a path of length $N$ from $x$ to $y$ achieved by the sequence of edges $(x_0{x}_1\mathrm{\cdots }{x}_N,x_1\mathrm{\cdots }{x}_N{y}_0)$, …$(x_N{y}_0\mathrm{\cdots }{y}_{N-1},y_0\mathrm{\cdots }{y}_N)$ unless $x_N=y_0$ in which case there is a similar path of length $N-1$ beginning $(x_0{x}_1\mathrm{\cdots }{x}_{N-1}{y}_0,x_1\mathrm{\cdots }{x}_{N-1}{y}_0{y}_1),\mathrm{\dots }$.)

$\bullet$ Kautz graphs are closely related to de Bruijn graphs, which are defined similarly but without the condition $s_i\ne s_{i+1}$, and with an alphabet of only $K$ symbols for the degree $K$ de Bruijn graph.

$\bullet$ For a fixed degree $K$ and number of vertices $V=(K+1)K^N$, the Kautz graph has the smallest diameter of any possible directed graph with $V$ vertices and degree $K$.

$\bullet$ 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)

$\bullet$ All Kautz graphs have a Hamiltonian cycle
(This result follows from the correspondence described above between edges of the Kautz graph ${𝒦}_K^N$ and vertices of the Kautz graph ${𝒦}_K^{N+1}$; a Hamiltonian cycle on ${𝒦}_K^{N+1}$ is given by an Eulerian cycle on ${𝒦}_K^N$)

$\bullet$ 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