Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
What's the difference between a walk and a path? –  Qiaochu Yuan Jan 4 '13 at 2:44
3  
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." –  Daniel Litt Jan 4 '13 at 2:44
6  
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. –  Richard Stanley Jan 4 '13 at 3:01
    
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). –  Shahrooz Jan 4 '13 at 8:53
add comment

3 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
1  
Which of course answers the original question for trees, since the only reduced walks are paths. –  Brendan McKay Jan 4 '13 at 13:55
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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