1
$\begingroup$

As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C_5$. How many $(x, y)$-paths of length $20$ are there?

$\endgroup$
  • 1
    $\begingroup$ A couple of clarifying questions: Is the graph only a $C_{5}$, or is there more to it? Do you mean a walk rather than a path? $\endgroup$ – Luke Mathieson Feb 18 '16 at 23:35
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help with conceptual problems but just solving homework-style exercises for you is unlikely to really help you. $\endgroup$ – David Richerby Feb 19 '16 at 0:59
  • 2
    $\begingroup$ @LukeMathieson "the cycle $C_5$" rather than "a 5-cycle" seems to be pretty unambiguous that the cycle is the whole graph. Agreed that it should be "walks" to avoid the answer being trivially zero. $\endgroup$ – David Richerby Feb 19 '16 at 1:00
  • $\begingroup$ @LukeMathieson Some of the literature uses "paths" and "simple paths" to refer to "walks" and "trails", respectively. So the question is on walks (which means the same as paths). $\endgroup$ – svsring May 30 '16 at 2:11
2
$\begingroup$

Hint: consider powers of adjacency matrix of $C_5$ (Wiki: Matrix powers).

$\endgroup$
1
$\begingroup$

You can use the fact that if $A$ is the adjacency matrix of a graph, then the $(i,j)$th entry of $A^k$ is the number of paths of length $k$ from vertex $i$ to vertex $j$. This fact can be proved by induction. So we need to obtain the $(1,2)$th entry of the matrix $A^{20}$. You can compute $A^{20}$ using a computer, or by hand by diagonalizing $A$ (observe that $A$ is a circulant matrix). A SAGE simulation (see below) gives the answer to be 204,820.

sage: c5=graphs.CycleGraph(5)
sage: A = c5.adjacency_matrix()
sage: A^20
[215766 204820 211585 211585 204820]
[204820 215766 204820 211585 211585]
[211585 204820 215766 204820 211585]
[211585 211585 204820 215766 204820]
[204820 211585 211585 204820 215766]
sage: 
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.