4
$\begingroup$

Suppose A is the adjacency matrix of a graph G. It is well known that the number of walks of length $\ell$ in G, from $v_i$ to $v_j$, is the entry in position $(i,j)$ of the matrix $A^\ell$. My question is that can we construct a matrix, say H, of a graph G, such that the number of paths of length $\ell$ in G, from $v_i$ to $v_j$, is the entry in position $(i,j)$ of the matrix $H^\ell$. If no, why?

$\endgroup$
4
  • $\begingroup$ What's the difference between a walk and a path? $\endgroup$ Jan 4, 2013 at 2:44
  • 3
    $\begingroup$ By a path do you mean a simple path? Whatever you mean, it seems to me that $H=H^1$ must satisfy that $H_{ij}$ is the number of paths of length $1$ between $v_i$ and $v_j$. For any reasonable definition of path, this is probably the same as the adjacency matrix, so if "path" and "walk" mean two different things, the answer is "no." $\endgroup$ Jan 4, 2013 at 2:44
  • 6
    $\begingroup$ It is highly unlikely that there is any simple computation to decide whether there is a path of length $\ell$ between two vertices (much less count how many such paths there are), since the existence of a path of length $p-1$, where $G$ has $p$ vertices, is NP-complete. $\endgroup$ Jan 4, 2013 at 3:01
  • $\begingroup$ For $P_3$ and induced $P_3$ there is a way, For graph $G$ and adjacency matrix $A$, the $diag(A^2)$ is the degree sequence of $G$. Now, the number of $P_3$ is: $N(P_3)=Cr(d(v_1),2)+\ldots +Cr(d(v_n),2)$. So, the number of induced $P_3$ is :$N(P_3)-3T_3(G)$, where $T_3(G)$ is the number of triangle in $G$. But, I can not thinking about $H$ that its power be smart as some combinatorial techniques. So, dear Stanley's answer is certainly true (in my opinion). $\endgroup$
    – Shahrooz
    Jan 4, 2013 at 8:53

3 Answers 3

3
$\begingroup$

Call a walk in $X$ reduced if it does not contain any subsequence of the form $uvu$, and let $p_r(A)$ denote the matrix whose $uv$-entry is the number of reduced walks from $u$ to $v$. Let $\Delta$ be the disgonal matrix such that $\Delta_{u,u}$ is the valency of $u$. Then if $r>2$, we have $$ Ap_{r-1}(A) = p_r(A) + (\Delta-I)p_{r-2}(A) $$ If $\Phi(X,t)$ is the generating function $\sum_r p_r(A)t^r$, it follows that $$ (I-tA+t^2(\Delta-I)) \Phi(X,t) = (1-t^2)I. $$ It follows that we can effectively count reduced walks. And if $X$ is a tree, then $\Phi(X,t)$ is actually a polynomial. [So $K_2$ is not a problem :-) ]

Of course I agree with Richard Stanley's remark about the general case.

$\endgroup$
1
  • 1
    $\begingroup$ Which of course answers the original question for trees, since the only reduced walks are paths. $\endgroup$ Jan 4, 2013 at 13:55
2
$\begingroup$

Let us take the graph G to be $K_2$. Your proposed H would have to be a zero matrix for all powers of H greater than 1. However, H would have to be nonnilpotent to record the paths of length 1. The upshot is that the path enumeration does not correspond to matrix multiplication. I would be surprised if any graphs G had an H that would work as you specify even for values of l at most 3.

Gerhard "Ask Me About System Design" Paseman, 2013.01.03

$\endgroup$
0
$\begingroup$

You can certainly do this by cheating and making an outrageous expansion of the set of vertices. Let the vertices of the original graph by $V$. Now you form a new directed graph with vertices $V\times \mathcal P(V)$ (where $\mathcal P$ denotes power set). For each edge $i\to j$ in the original graph, and for each set $S$ containing $i$ but not $j$, define an edge $(i,S)\to (j,S\cup\lbrace j\rbrace)$. This new monster graph keeps track of all the places you've been and only lets you visit new vertices.

Let $\bar A$ be the adjacency matrix of this new directed graph. Finally, let $B$ be the $|V|\cdot 2^{|V|}\times |V|$ matrix with $B_{j\times S,j}=1$ for each $S$, and 0 and equal to 0 for all other entries.

The number of walks from $i$ to $j$ in the original graph of length $l$ is given by $(A^lB)_{(i,\lbrace i\rbrace),j}$.

Of course, this is absolutely not a practical way to compute anything...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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