Distribution of cycles length in a graph
When $k = n$ and self-loops are allowed, what you have is a random permutation. The expected length of the longest cycle in a permutation is known to be $\alpha n$ for $\alpha \approx 0.624$, see Shepp and Lloyd. If self-loops are not allowed then you will get a different constant $\beta$ that can probably be computed using the methods of Shepp and Lloyd.

When $k &lt; n$, you just get a permutation on $k$ vertices, so instead of $\alpha n$ or $\beta n$ you would get $\alpha k$ or $\beta k$.