Operations of walk regular graphs

35 Views Asked by At

We have that a walk regular graph is one in which $A^k$ is a constant diagonal matrix for all $k \geq 0$.

Given this, do operations on walk regular graphs also result in walk regular graphs? For example do the cartesian product, direct product or complement of walk regular graphs also result in walk regular graphs? How might one go about providing things like this?

1

There are 1 best solutions below

2
On

This will depend on the operation, but essentially you could have (at least) two approaches.

One is to describe how the operation works on the adjacency matrix $A$ (for the complement) or the two adjacency matrices $A, B$ (for products); and then try to algebraically manipulate the expression for the resulting matrix $C$ (and $C^k$) to prove it is constant-diagonal using the assumption. This is probably easiest for the complement – what's an expression for the adjacency matrix of the complement, and what can you do with that expression taken to the $k$-th power?

Another approach is to characterize walks in the new graph, and use the graph-theoretic definition of walk-regular graphs (for all $k\geq 0$, the number of closed walks of length $k$ from $v$ to itself is the same for all $v$). This is probably easiest for the direct product of graphs $A \times B$, since k-walks in it correspond exactly to pairs of k-walks in $A$ and $B$. So if you known the number of closed k-walks in $A$ starting from any vertex is some constant $a_k$, and you know for $B$ it is $b_k$; then what is the number of pairs of closed $k$-walks starting from any vertex pair $(u, v) \in V(A) \times V(B)$?

For some operations the answer may be "false", so you just have to show a counter-example. The simplest one is for the disjoint union.