Intereting Posts

Transvection matrices generate $SL_n(\mathbb{R})$
A stronger version of discrete “Liouville's theorem”
Finding the correct contour to evaluate an integral with finite bounds of integration
There does not exist an entire function which satisfies $f({1\over n})={1\over 2^n}$?
Distribution of the sum of squared independent normal random variables.
If $S \times \Bbb{R}$ is homeomorphic to $T \times \Bbb{R}$ and $S$ is compact, can we conclude that $T$ is compact?
For $N\unlhd G$ , with $C_G(N)\subset N$ we have $G/N$ is abelian
It's in my hands to have a surjective function
Evaluate $\lim_{x\to \infty}\ (x!)^{1/x}$
How do you go about doing mathematics on a day to day basis?
Number of functions from n-element set to {1, 2, …, m}
Are these solutions of $2 = x^{x^{x^{\:\cdot^{\:\cdot^{\:\cdot}}}}}$ correct?
What is the first $w$ such that a rectangle, $R_{w\times w-1}$ is minimally-square-partitioned by less than $w$ squares.
Distance of two lines in $\mathbb{R}^3$
Exponential of a polynomial of the differential operator

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?

- Ramsey Number R(4,4)
- A binary sequence graph
- Small cycles in an undirected graph
- Maximum edges in a square free graph
- Condition on degrees for existence of a tree
- Not lifting your pen on the $n\times n$ grid

- if $G$ has a matching with $k$ edges, then it has a bipartite subgraph with $(|E(G)+k|)/2$ edges or more
- The use of any as opposed to every.
- How many cycles, $C_{4}$, does the graph $Q_{n}$ contain?
- Constructing self-complementary regular graphs
- Is the derivative of the characteristic polynomial equal to the sum of characteristic polynomial of principle submatrices?
- How many 2-edge-colourings of $K_n$ are there?
- Finding an MST among all spanning trees with maximum of white edges
- Isolated vertex probabilities for different random graphs
- Make up a reasonable definition for the bipartite complement of a bipartite graph
- Is there a nodeless graph?

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$.

- distribution of categorical product (conjunction) over coproduct (disjunction)
- How can $\mathbb{R}^n$ has the same number of dimentions of $\mathbb{S}^n$?
- Difference between logarithm of an expectation value and expectation value of a logarithm
- How to prove $\sum_{s=0}^{m}{2s\choose s}{s\choose m-s}\frac{(-1)^s}{s+1}=(-1)^m$?
- a function $f$ is differentiable in $\vec{0}$ if $f \circ \gamma $ is differentiable in 0
- minimal polynomial of power of algebraic number
- Numerical solution to a system of second order differential equations
- Commutator subgroup of a dihedral group.
- Rigorous Text in Multivariable Calculus and Linear Algebra
- About the determination of complex logarithm
- Limit in Definition of Riemann Integral is one-sided?
- prove equality with integral and series
- If $\left(1^a+2^a+\cdots+n^{a}\right)^b=1^c+2^c+\cdots+n^c$ for some $n$, then $(a,b,c)=(1,2,3)$?
- Given $p \equiv q \equiv 1 \pmod 4$, $\left(\frac{p}{q}\right) = 1$, is $N(\eta) = 1$ possible?
- Logic and Metamath book recommendation