# Kautz graph

The Kautz graph ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N+1}$ is a digraph^{} (directed
graph) of degree $K$ and dimension $N+1$, which has $(K+1)\beta \x81\u2019{K}^{N}$
vertices labeled by all possible strings ${s}_{0}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{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}\beta \x89{s}_{i+1}$).

The Kautz graph ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N+1}$ has $(K+1)\beta \x81\u2019{K}^{N+1}$ edges

$$\{({s}_{0}\beta \x81\u2019{s}_{1}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{s}_{N},{s}_{1}\beta \x81\u2019{s}_{2}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{s}_{N}\beta \x81\u2019{s}_{N+1})|{s}_{i}\beta \x88\x88A\beta \x81\u2019{s}_{i}\beta \x89{s}_{i+1}\}.$$ | (1) |

It is natural to label each such edge of ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N+1}$ as ${s}_{0}\beta \x81\u2019{s}_{1}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{s}_{N+1}$, giving a one-to-one correspondence between edges of the Kautz graph ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N+1}$ and vertices of the Kautz graph ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N+2}$.

Example:

The Kautz graph ${\mathrm{\pi \x9d\x92\xa6}}_{2}^{2}$ has 6 nodes, and is depicted in the following figure (using the alphabet $A$ ={0, 1, 2})

$\beta \x88\x99$
The diameter of the Kautz graph
${\mathrm{\pi \x9d\x92\xa6}}_{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}\beta \x81\u2019{x}_{1}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{x}_{N},{x}_{1}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{x}_{N}\beta \x81\u2019{y}_{0})$, β¦$({x}_{N}\beta \x81\u2019{y}_{0}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{y}_{N-1},{y}_{0}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{y}_{N})$ unless ${x}_{N}={y}_{0}$ in
which case there is a similar path of length $N-1$ beginning
$({x}_{0}\beta \x81\u2019{x}_{1}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{x}_{N-1}\beta \x81\u2019{y}_{0},{x}_{1}\beta \x81\u2019\mathrm{\beta \x8b\u2015}\beta \x81\u2019{x}_{N-1}\beta \x81\u2019{y}_{0}\beta \x81\u2019{y}_{1}),\mathrm{\beta \x80\xa6}$.)

$\beta \x88\x99$ Kautz graphs are closely related to de Bruijn graphs, which are defined similarly but without the condition ${s}_{i}\beta \x89{s}_{i+1}$, and with an alphabet of only $K$ symbols for the degree $K$ de Bruijn graph.

$\beta \x88\x99$ For a fixed degree $K$ and number of vertices $V=(K+1)\beta \x81\u2019{K}^{N}$, the Kautz graph has the smallest diameter of any possible directed graph with $V$ vertices and degree $K$.

$\beta \x88\x99$ 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)

$\beta \x88\x99$ All Kautz graphs have a Hamiltonian cycle^{}

(This result follows from the correspondence described above
between edges of the Kautz graph ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N}$
and vertices of the Kautz graph
${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N+1}$; a Hamiltonian cycle on ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N+1}$ is
given by an Eulerian cycle on ${\mathrm{\pi \x9d\x92\xa6}}_{K}^{N}$)

$\beta \x88\x99$ 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 |