On the \(k\)-diameter of \(k\)-regular \(k\)-connected graphs (Q1336711)

The authors study the \(k\)-diameter of \(k\)-regular \(k\)-connected graphs. The \(k\)-diameter of a graph \(G\) is the maximum diameter of the graphs obtained from \(G\) by removing \(k-1\) vertices. It is shown that every \(k\)- regular \(k\)-connected graph on \(n\) vertices has \(k\)-diameter at most \(n/2\) and this upper bound can be achieved at some graphs.