1 Answers
The Kautz graph K M N + 1 {\displaystyle K_{M}^{N+1}} is a directed graph of degree M {\displaystyle M} and dimension N + 1 {\displaystyle N+1} , which has M N {\displaystyle M^{N}} vertices labeled by allpossible strings s 0 ⋯ s N {\displaystyle s_{0}\cdots s_{N}} of length N + 1 {\displaystyle N+1} which are composed of characters s i {\displaystyle s_{i}} chosen froman alphabet A {\displaystyle A} containing M + 1 {\displaystyle M+1} distinctsymbols, subject to the condition that adjacent characters in thestring cannot be equal.
The Kautz graph K M N + 1 {\displaystyle K_{M}^{N+1}} has M N + 1 {\displaystyle M^{N+1}} edges
{ | s i ∈ A s i ≠ s i + 1 } {\displaystyle \{|\;s_{i}\in A\;s_{i}\neq s_{i+1}\}\,}
It is natural to label each such edge of K M N + 1 {\displaystyle K_{M}^{N+1}} as s 0 s 1 ⋯ s N + 1 {\displaystyle s_{0}s_{1}\cdots s_{N+1}} , giving a one-to-one correspondencebetween edges of the Kautz graph K M N + 1 {\displaystyle K_{M}^{N+1}} and vertices of the Kautz graph K M N + 2 {\displaystyle K_{M}^{N+2}}.