A Kautz graph is a labeled graph, vertices are labeled by strings of length
`n+1`

above an alphabet with `m+1`

letters, with the restriction
that every two consecutive letters in the string must be different. There is
a directed edge from a vertex `v`

to another vertex `w`

if it is
possible to transform the string of `v`

into the string of `w`

by
removing the first letter and appending a letter to it.

Kautz graphs have some interesting properties, see eg. Wikipedia for
details.