[seqfan] Re: closed walks in a complete graph

hv at crypt.org hv at crypt.org
Wed Aug 17 12:12:48 CEST 2022

I don't know the answer to your question, but I'm worried about your
total count of (n-1)^(k-1) - do you not have to ensure that the (k-1)'th
step did not itself land on the starting vertex?

For example when n=2 I think total count would be (1^k + (-1)^k) / 2.
If your total is wrong, it could be affecting your search for related


Brendan McKay via SeqFan <seqfan at list.seqfan.eu> wrote:
: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.
:Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list