This is a follow-up question to Characterisation of walk-equivalent digraphs.

Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that \begin{equation} tr(w(A_G,A_G^t)\cdot J)=tr(w(A_H,A_H^t)\cdot J) \tag{1}\label{eq:one} \end{equation} holds for every word $w(x,y)$? Intuitively, this condition states that $G$ and $H$ have the same number of semi-walks of a certain type (as described by $w(x,y)$), and this for any such type (i.e., any word $w(x,y)$).

Here, $A_G$ and $A_H$ are the adjacency matrices of $G$ and $H$, respectively, $J$ is the $n\times n$-matrix consisting of all ones. For a word $w(x,y)$, for example $w(x,y)=x.y.x$, $w(A_G,A_G^t)$ is interpreted as $A_G\cdot A_G^t\cdot A_G$.

Important restriction: There should not exist a doubly quasi-stochastic matrix $S$ (a matrix $S$ such that $S.\mathbf{1}=\mathbf{1}$ and $\mathbf{1}^t\cdot S=\mathbf{1}$ with $\mathbf{1}$ the $n\times 1$-vector consisting of all ones.) such that $A_G\cdot S=S\cdot A_H$.

In the answer https://mathoverflow.net/q/341573 to Characterisation of walk-equivalent digraphs a counter example was given such that $tr(A^k\cdot J)=tr(B^k\cdot J)$ holds for every $k\geq 0$. However, the example does not satisfy the more general condition (\ref{eq:one}).

Update: Note that since $A_G\cdot A_G^t$ and $A_H\cdot A_H^t$ are symmetric matrices, and (\ref{eq:one}) implies that $tr((A_G\cdot A_G^t)^k\cdot J)=tr((A_H\cdot A_H^t)^k\cdot J)$ for any $k\geq 0$, these matrices must be related by a doubly quasi-stochastic matrix $O$, i.e., $A_G\cdot A_G^t\cdot O=O\cdot A_H\cdot A_H^t$. Similarly for the symmetric matrices $A_G^t\cdot A_G$ and $A_H^t\cdot A_H$, possibly with another doubly quasi-stochastic matrix $O'$. This severely restricts candidate graphs. Perhaps this helps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.