Kautz graph

The Kautz graph , named after William H. Kautz (* 1924), is a digraph ( directed graph ) of degree and dimension with corners. The corners are marked with all possible character strings of the length of characters of the alphabet that contain different symbols, with the restriction that adjacent characters in the character string must not be the same ( for ). ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle M}$ ${\displaystyle N+1}$ ${\displaystyle (M+1)M^{N}}$ ${\displaystyle s_{0}\cdots s_{N}}$ ${\displaystyle N+1}$ ${\displaystyle A}$ ${\displaystyle M+1}$ ${\displaystyle s_{i}\neq s_{i+1}}$ ${\displaystyle i=0,\ldots ,N-1}$

The Kautz graph has directed edges ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle (M+1)M^{N+1}}$

${\displaystyle \{(s_{0}s_{1}\cdots s_{N},s_{1}s_{2}\cdots s_{N}s_{N+1})|s_{i}\in A,\;s_{i}\neq s_{i+1}\}}$

Usually these edges are marked with , which gives a 1: 1 correspondence between the edges of the Kautz graph and corners of the Kautz graph . ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle s_{0}s_{1}\cdots s_{N+1}}$ ${\displaystyle K_{M}^{N+1}}$ ${\displaystyle K_{M}^{N+2}}$

Kautz graphs are closely related to De Bruijn graphs .

properties

• For fixed degrees and number of vertices , the Kautz graph has the smallest possible diameter of a directed graph with vertices and degrees . ${\displaystyle M}$ ${\displaystyle V=(M+1)M^{N}}$ ${\displaystyle V}$ ${\displaystyle M}$
• All Kautz graphs have directed Euler circles
• All Kautz graphs have a directed Hamiltonian circle
• A Grad- Kautz graph has unconnected directed paths from any node to any other node . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle x}$ ${\displaystyle y}$

literature

• WH Kautz: Bounds on directed (d, k) graphs , Theory of cellular logic networks and machines, AFCRL-68-0668 SRI Project 7258 Final report, 1968, pp. 20-28
• WH Kautz: Design of optimal interconnection networks for multiprocessors , Architecture and design of digital computers, Nato Advanced Summer Institute, 1969, pp. 249-272.

Web links

• Kautz graph at planetmath.org