Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive nor distance-regular?

Question

The class of walk-regular graphs contains the vertex-transitive graphs and the distance-regular graphs. However, there are walk-regular graphs that are neither vertex-transitive nor distance-regular. In particular, I believe that I found a first example of a cubic walk-regular graph that is neither vertex-transitive nor distance-regular on 20 vertices: its Graph6 code is SsP@@?OC?S@C@_@C?K?A_?AG?D??C_??].

My question here is: are there only finitely many cubic walk-regular graphs (up to isomorphism) that are neither vertex-transitive nor distance-regular (or is it e.g. possible to construct an infinite family of graphs of this kind)?

There are e.g. only finitely many distinct cubic distance-regular graphs - could it e.g. also be true that there are only finitely many distinct non-vertex-transitive cubic walk-regular graphs?

Answer 1

A graph is called semisymmetric if it is regular, edge-transitive but not vertex-transitive.

Semisymmetric graphs are walk-regular hence they provide example of graphs that are regular and walk-regular but not vertex-transitive.

This answers your question, as it is known that there are infinitely many semisymmetric cubic graphs (I could probably dig up a reference for this if you need), and, as you note, only finitely many of these can be distance-regular.

Krystal Guo and I noticed this last year (and even e-mailed Brendan about it) but deemed it too minor to write it up.

Answer 2

This is a good question and I'm fairly sure the answer is not known. My collection of non-transitive cubic connected walk-regular graphs looks like this:

  1 graphs : n=20; girth=6; bipartite; radius=4; diameter=5; orbits=2
  1 graphs : n=30; girth=6; bipartite; radius=5; diameter=5; orbits=3
  1 graphs : n=32; girth=6; bipartite; radius=5; diameter=6; orbits=2
  1 graphs : n=60; girth=3; not bipartite; radius=8; diameter=10; orbits=3
  1 graphs : n=1200; girth=3; not bipartite; radius=19; diameter=20; orbits=3
  1 graphs : n=3600; girth=3; not bipartite; radius=22; diameter=22; orbits=3

I've had them for several years but never got around to publishing them.

The list is complete up to 30 vertices, and for 32 vertices it is complete for triangle-free cubic graphs.

Answer 3

What follows is a proof that semisymmetric graphs are walk-regular.

Say vertices $u$ and $v$ in a graph $X$ are cospectral if the graphs $X\setminus u$ and $X\setminus v$ are cospectral. If $X$ is semisymmetric, then the vertices in each colour class are cospectral. Two vertices $u$ and $v$ in a bipartite graph are cospectral if, for each non-negative integer $k$, the number of closed walks of length $2k$ starting at $u$ equals the number starting at $v$. [This is proved, for example, in Section 8.13 in one of my favourite texts on algebraic graph theory. :-)]

The adjacency matrix $A$ of any bipartite graph can be written in the form \[ A =\begin{pmatrix}0&B\\ B^T&0\end{pmatrix} \] and hence \[ A^{2k} = \begin{pmatrix}(BB^T)^k&0\\ 0&(B^TB)^k&\end{pmatrix} \] Since $X$ is semisymmetric, the diagonal entries of $(BB^T)^k$ are all equal, as are the diagonal entries of $(B^TB)^k$.

By the cyclic symmetry of trace, we see that $(BB^T)^k$ and $(B^TB)^k$ have the same trace. Therefore the diagonal entries of these two matrices are equal, and it follows that $X$ is walk regular.