Number of edges with shortest cycle k in a Kautz graph

Abstract

For the Kautz digraph $K(d,D)$, let ${\rho }_k(d,D)$ be the number of oriented edges whose shortest directed cycle has length $k+1$, and define ${\Delta }_k(d,D)={\rho }_k(d,D)-{\rho }_k(d,D-1)$. We give an exact, finite-dimensional matrix product that computes ${\Delta }_k(d,D)$ directly, without first computing $\rho$. In particular, ${\Delta }_k(d,D)=0$ for $k<D/2+2$. and ${\Delta }_k(d,D)$ is positive for every larger $k$ up to $D-1$.

5 pages