Kautz-Graph
# Kautz-Graph

Der Kautz-Graph $K_{M}^{N+1}$, benannt nach William H. Kautz (* 1924), ist ein Digraph (gerichteter Graph) vom Grad $M$ und Dimension $N+1$ mit $(M+1)M^{N}$ Ecken. Die Ecken sind bezeichnet mit allen möglichen Zeichenketten $s_{0}\cdots s_{N}$ der Länge $N+1$ aus Zeichen des Alphabets $A$, das $M+1$ unterschiedliche Symbole enthält, mit der Einschränkung, dass nebeneinander gelegene Zeichen in der Zeichenkette nicht gleich sein dürfen ($s_{i}\neq s_{i+1}$ für $i=0,\ldots ,N-1$).

Der Kautz-Graph $K_{M}^{N+1}$ hat $(M+1)M^{N+1}$ gerichtete Kanten

$\{(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}\}$

Normalerweise markiert man diese Kanten von $K_{M}^{N+1}$ mit $s_{0}s_{1}\cdots s_{N+1}$, wodurch man eine 1:1-Entsprechung zwischen Kanten des Kautz-Graphen $K_{M}^{N+1}$ und Ecken des Kautz-Graphen $K_{M}^{N+2}$ erhält.

Kautz-Graphen sind eng verwandt mit De-Bruijn-Graphen.

## Eigenschaften

* Für festen Grad $M$ und Anzahl der Ecken $V=(M+1)M^{N}$ hat der Kautz-Graph den kleinsten möglichen Durchmesser eines gerichteten Graphen mit $V$ Ecken und Grad $M$.
* Alle Kautz-Graphen haben gerichtete Eulerkreise
* Alle Kautz-Graphen haben einen gerichteten Hamiltonschen Kreis
* Ein Grad-$k$ Kautz-Graph hat $k$ unverbundene gerichtete Wege von beliebigem Knoten $x$ zu beliebigem anderen Knoten $y$.
