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

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?

• I expect you mean "connected finite graph" when you say "graph"? – YCor Mar 8 '17 at 3:52
• Yeah, what I'm really implicitly meaning with my question(s) is connected finite simple graph, I suppose. – m4farrel Mar 8 '17 at 3:59

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.

• Semisymmetric graphs are walk regular. – Chris Godsil Mar 8 '17 at 13:16
• Hi Gabriel, Yes I had completely forgotten your correspondence from last September. Thanks for the reminder. – Brendan McKay Mar 8 '17 at 23:55
• Thank you for your answer. I think this may answer my question, but perhaps still leaves me with another question: are there only finitely many distinct cubic walk-regular graphs that are neither vertex-transitive, edge-transitive, nor distance-regular? – m4farrel Mar 9 '17 at 0:41
• More generally, I'd perhaps wonder if some kind of structural characterization of (cubic) walk-regular graphs is possible? – m4farrel Mar 9 '17 at 0:43
• @m4farrel I don't know the answer to your other question. (The less symmetry involved, the less I know.) If I had to guess, I would say yes. As for a structual characterisation, I don't know, but since that class includes all vertex-transitive and edge-transitive graphs, that seems a bit unlikely? – verret Mar 9 '17 at 0:46

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.

• Is your list known to be complete up to any number of vertices? – Gordon Royle Mar 8 '17 at 5:00
• @GordonRoyle : added – Brendan McKay Mar 8 '17 at 5:35
• Thank you for your response. Do you happen to have e.g. Graph6 codes for your examples here, so that I can e.g. have a closer look at these graphs and their properties? – m4farrel Mar 9 '17 at 0:28
• @m4farrel Sure, just send me email. brendan.mckay AT anu.edu.au . – Brendan McKay Mar 9 '17 at 0:31
• Also, I think that it may be worth mentioning that every regular triangle-free connected graph with at most six distinct eigenvalues is walk-regular - and, in particular, the the first example on 20 vertices that I found falls into this family of walk-regular graphs (it is triangle-free with { +/- 1, +/- 2, +/- 3} as its set of eigenvalues). – m4farrel Mar 9 '17 at 0:32

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.