Asymptotically optimal \((\Delta, D', s)\)-digraphs (Q2713607)

Starting with the de Bruijn digraph \(B(\Delta , D)\) and the Kautz digraph \(K(\Delta , D)\)---vertices of \(B\) are the words \(z_1z_2\ldots z_D\in \{1, 2, \ldots , \Delta \}^D\), in \(K\) we have the alphabet \(\{1, 2, \ldots , \Delta +1\}\) and \(z_i\neq z_{i+1}\) is required, and \(z_1z_2\ldots z_D\rightarrow z_2\ldots z_Dz_{D+1}\) in both---the authors introduce digraphs \(K(\Delta _1, D-1)\times K(\Delta _2, D-1)\) and \(B(\Delta _1, D-1)\times K(\Delta _2, D-1)\); here \(\times \) is the cartesian product of digraphs (\((a,b)\rightarrow (c,d)\) iff \(a\rightarrow c\) and \(b\rightarrow d\)). Both digraphs are \(\Delta _1\Delta _2\)-regular. They prove that both digraphs have diameter \(D\) and that the diameter does not increase when at most \((\Delta_1-1)(\Delta _2-1)-2\) vertices are deleted from the former digraph and the same if at most \(\Delta _1(\Delta _2-1)-2\) vertices are deleted from the latter digraph. They also consider the more general digraph \(B(\Delta , D)\times G\), where \(G\) is any digraph. Tables of orders of largest known \((\Delta ,D',s)\)-digraphs (out-degree is at most \(\Delta \) and after the deletion of any \(s\) vertices the diameter is at most \(D'\)) are given.