PlanetMath: Kautz graph

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Kautz graph

(Definition)

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

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

$\displaystyle \{(s_0 s_1 \cdots s_N, s_1 s_2 \cdots s_N s_{N + 1})\vert \; s_i \in A \; s_i \neq s_{i + 1} \} .$

(1)

It is natural to label each such edge of ${\cal K}_K^{N + 1}$ as $s_0s_1 \cdots s_{N + 1}$ , giving a one-to-one correspondence between edges of the Kautz graph ${\cal K}_K^{N + 1}$ and vertices of the Kautz graph ${\cal K}_K^{N + 2}$ .

Example:

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

$\includegraphics{C:wati22-8.eps}$

Properties:

$\bullet$ The diameter of the Kautz graph ${\cal K}_K^{N}$ is
(For example, there is a path of length from to achieved by the sequence of edges $(x_0 x_1 \cdots x_N, x_1 \cdots x_N y_0)$ , ... $(x_N y_0 \cdots y_{N -1}, y_0 \cdots y_N)$ unless in which case there is a similar path of length beginning $(x_0 x_1 \cdots x_{N-1} y_0, x_1 \cdots x_{N-1} y_0 y_1), \ldots$ .)

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

$\bullet$ For a fixed degree and number of vertices , the Kautz graph has the smallest diameter of any possible directed graph with vertices and degree .

$\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 ${\cal K}_K^{N}$ and vertices of the Kautz graph ${\cal K}_K^{N + 1}$ ; a Hamiltonian cycle on ${\cal K}_K^{N + 1}$ is given by an Eulerian cycle on ${\cal K}_K^{N}$ )

$\bullet$ A degree- Kautz graph has disjoint paths from any node to any other node .

"Kautz graph" is owned by wati.

(view preamble)