Graphs whose degree vectors coincide for all powers of their adjacency matrices

Question

Let symmetric $A,B \in \{0, 1\}^{n \times n}$ denote the adjacency matrices of two simple graphs. Further let $\mathbf{1}$ denote the all-one-vector.

Now assume that $A^k \mathbf{1} = B^k \mathbf{1}$ for all $k \geq 0$. $\quad (\star)$

That is, the graphs $A$ and $B$ have the same degree vector, and this even holds true for all powers of their adjacency matrices. Since $A^k_{ij}$ also gives the number of walks in $A$ from vertex $i$ to vertex $j$ of length exactly $k$, similar for $B^k_{ij}$, this strongly relates the structures of $A$ and $B$ to each other.

What is known about this relation between $A$ and $B$? Is there some concept from algebraic graph theory, spectral graph theory, or linear algebra, that captures $(\star)$ exactly, or at least as a non-trivial sufficient or necessary property?

Answer 1

As I mentioned in a comment. Two $n$-vertex graphs , both regular of degree $d$ , will have this property, although the graphs can be quite different in some ways, for example one may be connected and the other not. I generalize this below. I believe that my construction is the same as that of Chris Godsil.

An aside: These graphs need not have the same spectrum. The condition of having the same spectrum is equivalent to $\operatorname{trace}(A^k)=\operatorname{trace}(B^k)$, having the same number (in total) of closed walks, for each $k$. However that condition does not even require equal degrees.

Regular graphs are the case $m=1$ of the following construction: Stipulate that the vertices will be in $m$ disjoint color classes with $n_i$ of color $c_i$ (so $n_1+n_2+\cdots+n_m=n$) and that each vertex of color $c_i$ has $d_{ij}$ edges going to vertices of color $d_j$ (so one much have $n_id_{ij}=n_jd_{ji}$.) Chosen correctly this gives great latitude to construct pairs or even families of graphs with equal parameters.

For example two bipartite graphs each with $6$ "red" vertices connected to $d_{12}=5$ out of $10$ "blue" vertices (each connected to $d_{21}=3$ of the red vertices). If desired, also connect each blue vertex to $d_{22}$ other blue vertices and each red to $d_{11}$ other red.

From the matrix viewpoint, the yet to be specified matrices are give an identical block structure with $m^2$ blocks with both $A_{ij}$ and $B_{ij}$ being an $n_i \times n_j$ $0,1$ matrix with all rows and columns having equal sums $c_{ij}$ and $c_{ji}.$ Of course $A_{ij}^t=A_{ji}$ and $A_{ii}$ has $0$ diagonal.

In the more standard language of algebraic graph theory, we have two graphs on $n$ vertices with equitable partitions, both giving the $m \times m$ quotient matrix with entries $c_{ij}.$

---

One subcase of $n_1=n_2=\cdots=2$ is to make $A$ with blocks $$\begin{array} c\\ 0&0\\0&0\\\end{array}$$ and $$\begin{array} c\\ 1&0\\0&1\\\end{array}$$ This is then the adjacency matrix of two disjoint copies of some graph $G.$ Leave this as it is -or- arbitrarily replace some of the identity matrices by $$\begin{array} c\\ 0&1\\1&0\\\end{array}$$ To get $B,$ do similar switches, just being sure not to have an isomorphic graph.

---

I suspect that it is possible to find an example with two graphs, each with an equitable partition, where the corresponding cells have the same size but the quotient matrices are not identical. However I have not managed to do so. A nice may to have this happen (since the graphs should not be regular) is if $A^2\mathbf{1}=B^2\mathbf{1}=c\mathbf{1}$ for some $c.$

Answer 2

I show that in some cases, the condition $A^k\textbf{1}=B^k\textbf{1}$ for all $k$ implies the graphs are isomorphic. For an $n$-vertex graph with adjacency matrix $A$ define its walk matrix to be the $n\times n$ matrix with columns $A^k\textbf{1}$ for $k=0,\ldots,n-1$.

Assume that $X$ and $Y$ are graphs with the same walk matrix $W$, and suppose $W$ is invertible.

If $W$ is the walk matrix of a graph $X$, then $AW=WC$ for some matrix $C$ and if $W$ is invertible, $C$ is the companion matrix of the characteristic polynomial of $A$. So if $X$ and $Y$ are graphs with the same walk matrix, they have the same characteristic polynomial, i.e., they are cospectral. If $\bar{A}$ is the adjacency matrix for the complement of $X$, then $W$ is also $\bar{A}$-invariant. It follows that if $X$ and $Y$ have the same walk matrix, and this matrix is invertible, then $X_1$ and $X_2$ are cospectral and their complements are cospectral too. Therefore, by a theorem of Johnson and Newman, there is an orthogonal matrix $L$ such that $A_2=L^TA_1L$ and $L\textbf{1}=\textbf{1}$. Now $$ B^k\textbf{1} = L^TA^kL\textbf{1} = L^TA^k\textbf{1} $$ and therefore $W=L^TW$. Since $W$ is invertible, $L=I$. [Most of this is in my paper at arXiv:1010.3231v1]