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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ What's the difference between a walk and a path? $\endgroup$– Qiaochu YuanCommented 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$– Daniel LittCommented 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$– Richard StanleyCommented 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$– ShahroozCommented Jan 4, 2013 at 8:53
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
answered Jan 4, 2013 at 3:41
-
1$\begingroup$ Which of course answers the original question for trees, since the only reduced walks are paths. $\endgroup$ Commented Jan 4, 2013 at 13:55
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
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...
answered Jan 4, 2013 at 4:01