[seqfan] Re: closed walks in a complete graph

[Brendan McKay]

Ooops.  Thanks, Hugo, you are right.

The simplest way to count all closed walks is to recall that the
adjacency matrix has 1 eigenvalue equal to n-1 and all others
equal to -1.  So, for closed walks of length k starting at one
vertex the count is
     (  (n-1)^k + (-1)^k (n-1) ) / n.

Cheers, Brendan.

On 17/8/2022 8:12 pm, hv at crypt.org wrote:
> 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
> sequences.
>
> Hugo
>
> 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/