My intuition tells me that there is always a unique, single shortest path between any two nodes in a Kautz di-graph. Is this true ? If yes, why? If not, why not ?

My intuition is based on the fact that Kautz graphs are best known optimal degree-diameter digraphs, that is, for a given degree (d>2) and diameter the Kautz graphs are the largest known graphs. So in this sense, one could argue that Kautz graphs do not "waste" shortest path connections.


For two nodes labeled $w_1$ and $w_2$ there will always be a largest $n$ such that the last $n$ symbols in $w_1$ are the same as the first $n$ symbols in $w_2$. The unique shortest path from $w_1$ to $w_2$ then arises by shifting in the rest of the symbols in $w_2$ one by one -- clearly doing anything else will just send us on a detour.

In the particular case that $n=0$ we just need to check that we're allowed to start by shifting in the first symbol of $w_2$ -- but the only reason we wouldn't be would be if the first symbol of $w_2$ is the same as the last symbol of $w_1$, and then $n$ would be at least $1$.

  • $\begingroup$ Many thanks Henning, I will sit down and think this over ... next to a nice cup of tee during the weekend. $\endgroup$ – jhegedus Nov 19 '15 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.