Digraf K(d, D) que té per conjunt de vèrtexs el de totes les paraules de longitud D que es poden formar amb els d + 1 símbols diferents d’un alfabet, de manera que dos símbols consecutius sempre siguin diferents.
Una paraula és adjacent respecte a una altra si la primera sense el símbol inicial és igual a la segona sense el símbol final. El digraf de Kautz K(d,D) té diàmetre D.