Kautz graph

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

...
Wikipedia