[seqfan] closed walks in a complete graph

Brendan McKay Brendan.McKay at anu.edu.au
Wed Aug 17 10:33:07 CEST 2022


Take a complete graph with n vertices and fix a starting vertex.

The number of closed walks of length k (i.e. k steps) from that vertex
to itself is (n-1)^(k-1), since we can walk arbitrarily for k-1 steps and
then return to the start on the k-th step.

How many closed walks of length k use exactly r distinct edges?

An example of a closed walk of length 4 using 2 distinct edges is u-v-w-v-u.

It must be known but I don't find it in OEIS.

Thanks, Brendan.




More information about the SeqFan mailing list