Kautz-Graph

The Kautz graph, named after William H. Kautz (* 1924) is a digraph ( directed graph ) of degree and dimension with corners. The corners are labeled with all possible strings of length from characters of the alphabet, which contains different symbols, with the restriction that adjacent points of characters in the string must not be the same ( for ).

The Kautz graph has directed edges

Normally you liked these edges with of, obtaining a 1:1 correspondence between the edges of the Kautz graphs and corners of the Kautz graph.

Kautz graphs are closely related to the de Bruijn graph.

Properties

• For fixed degree and number of vertices of the Kautz graph has the smallest possible diameter of a directed graph with vertices and degrees.
• All Kautz graphs have directed Euler circuits
• All Kautz graphs have a directed Hamiltonian cycle
• A degree Kautz graph has disconnected directed paths from any node to any other node.