Timeline for power of adjacency matrix
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 4, 2013 at 8:53 | comment | added | Shahrooz | 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). | |
| Jan 4, 2013 at 4:01 | answer | added | Anthony Quas | timeline score: 0 | |
| Jan 4, 2013 at 3:41 | answer | added | Chris Godsil | timeline score: 3 | |
| Jan 4, 2013 at 3:02 | answer | added | Gerhard Paseman | timeline score: 2 | |
| Jan 4, 2013 at 3:01 | comment | added | Richard Stanley | 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. | |
| Jan 4, 2013 at 2:44 | comment | added | Daniel Litt | 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." | |
| Jan 4, 2013 at 2:44 | comment | added | Qiaochu Yuan | What's the difference between a walk and a path? | |
| Jan 4, 2013 at 2:39 | history | asked | Tylar Liu | CC BY-SA 3.0 |