On the diameter vulnerability of Kautz digraphs (Q1916380)

Suppose \(a\) and \(b\) are integers with \(a \leq b\) and \(c(a,b)\) is the set of consecutive integers from \(a\) to \(b\) inclusively. Let \(V\) be the set of vectors with \(t\) components each in \(c(0,d)\) such that any two adjacent components are distinct. The authors define the Kautz digraph \(K(d,t)\) as the digraph with vertex set \(V\) and arc set consisting of all arcs from the vertex \((x_1, x_2, \dots, x_t)\) to \(d\) other vertices \((x_2, x_3, \dots, x_t, \alpha)\) where \(\alpha\) is in \(c(0,d)\), \(\alpha \neq x_t\). It is shown that in \(K(d,t)\) with \(d^t + d^{t - 1}\) vertices each having out degree \(d\), there exist \(d\) vertex disjoint paths between any pair of distinct vectors, one of length at most \(t\), \(d - 2\) of length at most \(t + 1\), and one of length at most \(t + 2\).