Intereting Posts

Proving $(0,1) $ is not countable
Are these two statements equivalent?
Intersection of two open dense sets is dense
Inverse Laplace transform of fraction $F(s) = \large\frac{2s+1}{s^2+9}$
Why do the $n \times n$ non-singular matrices form an “open” set?
The compact-open topology on the Pontryagin dual is the weakest topology that make all Fourier transforms continuous
3 primes conjecture
Is $\frac00=\infty$? And what is $\frac10$? Are they same? Does it hold true for any constant $a$ in $\frac{a}0$
How to show $\gamma$ aka Euler's constant is convergent?
Ring with finitely many zerodivisors
Tell Wolfram Alpha that a variable is a natural number
What is a geometric explanation of complex integration in plain English?
Why is Peano arithmetic undecidable?
The use for solving quadradic equations for high school students
Finding subgroups of a free group with a specific index

Sorry for bad English.

Consider a graph $G$ with the adjacency matrix $A$. I know that the number of paths of the length $n$ is the sum of elements $A^n$.

But what if we can’t walk through a vertex more than one times?

- Counting simple, connected, labeled graphs with N vertices and K edges
- Can we get the line graph of the $3D$ cube as a Cayley graph?
- Graph Run Time, Nodes and edges.
- understanding the basic definition
- Prove that graph has at least one cycle of length at least $\delta+1$
- eigen decomposition of an interesting matrix (general case)

- Ramsey Number R(4,4)
- Arrangement of integers in a row such that the sum of every two adjacent numbers is a perfect square.
- Adjacency matrix and connectivity proof
- What's the relation between topology and graph theory
- Known bounds and values for Ramsey Numbers
- Existence of k-regular graph
- On the number of caterpillars
- Graph theory software?
- Moscow puzzle. Number lattice and number rearrangement. Quicker solution?
- All tree orders are lattice orders?

There doesn’t seem to be a simple expression involving the adjacency matrix for the number of simple (i.e. self-avoiding) paths in an arbitrary graph, but there is an algorithm.

Googling “adjacency matrix number of paths” turned up this SE question which points out (with a nice example) that powers of the adjacency matrix count the number of *walks* of length $n$, not paths. That fact also turned up in this wikipedia entry. These walks allow a vertex to be visited more than once, so it’s unlikely they can help you to count simple paths.

The paper Self-Avoiding Paths and the Adjacency Matrix of a Graph – J. Ponstein contains an algorithm on pages 9-10 which counts all simple paths in an arbitrary graph.

**Edit**: The good news is explicit formulae for the paths of length $n$ exist, the bad news is the number of terms in the formulae grow exponentially with $n$!

The paper On the determination of redundancies in sociometric chains – Ross, Ian C.; Harary, Frank counts the number of ‘redundant paths’ (i.e. non-simple paths, walks of length $n$ where a vertex is visited more than once).

The English language powerpoint slideshow of the Russian language paper “The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths” by S. N. Perepechko & A. N. Voropaev contains formula for path lengths 2-5 using the Ross & Harary method. I reproduce, for your delectation or horror, 2 of the 17476 terms from the path length 10 formula ($\times$ is element-wise matrix multiplication, $\cdot$ is ordinary matrix multiplication):

[**This is a counter-example to wece’s answer, posted only as an answer because it’s too long for a comment.**]

wece’s method is **only** correct for $A_2$. Counterexample: Let $A=\left[\begin{array}{ccccc}0&1&0&0&0\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{array}\right]$ representing a chain of 5 vertices connected by 4 edges. $A_1=A-diag(A)=A$.

$A_2=A\otimes A_1 =\left[\begin{array}{ccccc}1&0&1&0&0\\0&2&0&1&0\\1&0&2&0&1\\0&1&0&2&0\\0&0&1&0&1\end{array}\right]$.

In $A_2$ we see all the paths of length 2, the diagonal representing forbidden paths of length 2 from each vertex back to itself, the off-diagonal entries representing the 8 paths of length 2 (path from $a \rightarrow b$ distinct from $b \rightarrow a$). Then

$A_3 = A \otimes A_2 = \left[\begin{array}{ccccc}0&1&0&0&0\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\0&0&0&1&0\end{array}\right]\left[\begin{array}{ccccc}0&0&1&0&0\\0&0&0&1&0\\1&0&0&0&1\\0&1&0&0&0\\0&0&1&0&0\end{array}\right] = \left[\begin{array}{ccccc}0&0&0&1&0\\1&0&1&0&1\\0&1&0&1&0\\1&0&1&0&1\\0&1&0&0&0\end{array}\right]$,

which according to wece’s method represents 10 paths of length 3, when there should be 3 such paths.

Let $A\otimes B$ be defined as the product of matrices where you removed the diagonal i.e.:

$$A\otimes B=(A-diag(A))\times(B-diag(B))$$

Let $A_1=A$ and $A_n=A\otimes A_{n-1}$.

The number of paths of the length n without going through a vertex more than one times is equal to the sum of elements of $A_n$.

- How to solve $\int_0^{\infty}\frac{x^n}{(x^2+1)^n}\,\mathrm dx$ for $n\ge 2$?
- Evaluate the integral using the theory of residues: $\int_{-\infty}^{\infty} \frac{dx}{(x^2+1)^2(x^2+16)}$
- How to prove Left Riemann Sum is underestimate and Right Riemann sum is overestimate?
- Finite set of zero-divisors implies finite ring
- How prove this irrational $x\in(0,1)$,then have $0<x-\sum_{i=1}^{n}\frac{1}{p_{i}}<\frac{1}{n!(n!+1)}$
- continuous map on $\mathbb{R}$ which is the identity on $\mathbb{Q}$ is the identity map, hence Aut$(\mathbb{R}/\mathbb{Q})= 1.$
- A proof that powers of two cannot be expressed as the sum of multiple consecutive positive integers that uses binary representations?
- Proving a function is continuous for a fixed variable
- Norm computation in number fields
- Algorithm for reversion of power series?
- Most useful heuristic?
- Find all roots of a polynomial using secant method
- How to deal with a Pell's equation type problem with two primes
- If point is zero-dimensional, how can it form a finite one dimensional line?
- how to prove that multiplication of points of an elliptic curve can be done with division polynomials