Kautz graph

The Kautz graph ${𝒦}_K^{N+1}$ is a digraph (directedgraph) 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 thatadjacent 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 correspondencebetween 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 thefollowing 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 thesequence 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$ inwhich 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 aredefined similarly but without the condition $s_i\ne s_{i+1}$, andwith 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$, theKautz graph has the smallest diameter of any possible directed graphwith $V$ vertices and degree $K$.

$\bullet$ All Kautz graphs have Eulerian cycles
(An Eulerian cycleis one which visits each edge exactly once– This result followsbecause Kautz graphs have in-degree equal to out-degree for eachnode)

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

$\bullet$ A degree-$k$ Kautz graph has $k$ disjointpaths from any node $x$to any other node $y$.