A Kautz graph is a regular directed graph derived from a de Bruijn graph on an alphabet of m>=3 letters using words of length n>=2 by deleting words containing two or more consecutive identical letters. For example, the (3, 3)-Kautz graph is illustrated above. (m, n)-Kautz graphs for m = 2 to 4 and n = 1 to 3 are illustrated above. Kautz graphs are Eulerian and Hamiltonian. The (m, n)-Kautz graph has vertex count m(m - 1)^(n - 1), graph diameter n, and vertex degree 2(m - 1). The Kautz graphs have the smallest possible graph diameter among all directed graphs for any fixed degree and number of vertices.

de Bruijn graph