I have a set of adjacency matrices that have a certain property, and I am trying to figure out what features of the adjacency matrix deliver that property and whether this property has a name.
Here is the property: Let $A$ be an adjacency matrix for an undirected graph. Such a matrix has Property $X$ if all the diagonal elements of $A$ are the same (which of course they are trivially), all the diagonal elements of $A^2$ are the same, all the diagonal elements of $A^3$ are the same, and so on for all powers of $A$.
Another way of describing this property is that for each node $i$, there are the same number of walks of length $k$ from node $i$ to itself for all $k$.
Thanks!
Best Answer
The usual name for this property is walk regular. and google will quickly lead to a lot of information. Clearly any vertex-transitive graph is walk regular, more generally any graph that is a union of classes from an association scheme. Connected regular graphs with exactly four eigenvalues are another class. I do not know of a characterization of walk-regular graphs that is much better than the definition.