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?

  • $\begingroup$ It is sufficient that both graphs are regular of degree $d$ and have the same number $v$ of vertices. With $d,v=3,20$ one has an icosahedron, a decagonal prism, the disjoint union of various cubic graphs and much more. $\endgroup$ – Aaron Meyerowitz Dec 2 '14 at 16:05
  • $\begingroup$ Yes, it holds that $C^k \mathbf{1} = d^k \mathbf{1}$ for every $d$-regular graph $C$. Intuitively, this is because the $i$'th entry in the vector $A^k\mathbf{1}$ equals the number of all walks of length exactly $k$ from vertex $i$ to anywhere. In a $d$-regular graph, a walk of length $l$ forks at each step into exactly $d$ different walks of length $l+1$. So for any $i$ there are exactly $d^k$ many walks of length $k$ started at $i$. I agree that this should be considered as non-trivial in the OP. But... is $d$-regularity also necessary? $\endgroup$ – cubic lettuce Dec 2 '14 at 19:23
  • $\begingroup$ A related question is mathoverflow.net/questions/84091/… $\endgroup$ – Gerry Myerson Dec 2 '14 at 23:28

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


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]

  • $\begingroup$ Your answer raises three questions to me: (1) How do you get $A^kP=PB^k$ from $AP=PB$ ? (2) I don't see any difference to Aaron's construction; aren't his "color classes" just a synonym for "cells" ? (3) If there is any cell with $\geq 2$ vertices, then $W$ has two coinciding rows, hence it is not invertible. Assuming that $W$ is invertible (almost) trivializes the isomorphic statement, since it implies the existence of $d=n$ individual cells ? $\endgroup$ – cubic lettuce Dec 3 '14 at 20:42
  • $\begingroup$ @user27164: As for Aaron's cells, you can sort that out with him, I've deleted that material. This may make the proof clearer - it does not involve partitions. $\endgroup$ – Chris Godsil Dec 3 '14 at 23:25
  • $\begingroup$ @user27164 if $AP=PB$ then $A^2P=A(AP)=APB=PBB$ etc. Consider 3 classes of graph matrices 1) A has a partner B 2) A has a non trivial equitable partition 3) the associated matrix W has full rank. Chris has a theorem that 1 & 3 are disjoint . You observe that 2&3 are disjoint. A 4-cycle shows that 2 is not a subset of 1. I'd love to know if 1 is a subset of 2 and , if so, if pairs from 1) must have equal reduced matrices. $\endgroup$ – Aaron Meyerowitz Dec 4 '14 at 2:02

Your Answer

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

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