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
up vote 8 down vote accepted

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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