A walk-regular graph is a simple graph whose vertices are all cospectral, which is characterized in terms of graph theory by the simple graphs where the number of closed walks of any length from a vertex to itself on said kind of simple graph is independent of the choice of vertex. Walk-regular graphs are interesting because they are a class of simple graphs that contain both the vertex-transitive graphs and distance-regular graphs - two relatively familiar examples of important classes of simple graphs in the context of algebraic graph theory. Not only do walk-regular graphs contain the vertex-transitive graphs and distance-regular graphs, but the class of walk-regular graphs also enjoys a number of arguably nice formal properties: e.g. complements of walk-regular graphs are again walk-regular, categorical products of walk-regular graphs are again walk-regular, Cartesian products of walk-regular graphs are again walk-regular, and so on. However, there doesn’t seem to be much concrete information available about walk-regular graphs themselves, despite the fact that the class of walk-regular graphs known to contain these two familiar classes of graphs and is also closed under a number of graph operations; in particular, there doesn’t seem to be much concrete information available about walk-regular graphs that are neither vertex-transitive nor distance-regular. In this post, I would like to provide some concrete examples of walk-regular graphs that I have found that are neither vertex-transitive nor distance-regular with the aid of computer - motivated by the high-level desire to gain a better intuition about what the class of walk-regular graphs looks like as a whole outside of these two familiar subclasses of graphs, and perhaps to potentially advance the theory of walk-regular graphs in general.

With the aid of a computer, I found that the first examples of walk-regular graphs that are neither vertex-transitive nor distance-regular are given on 12 vertices. In particular, I found that there are 4 of them (up to isomorphism). Here are their Graph6 codes:

  • KU`OXC`XKpHW
  • KCOfeqkfJkLg
  • KCpfJrs]lyRw
  • KCzbrj{{}}Vw

There appears to be no examples of walk-regular graphs that are neither vertex-transitive nor distance-regular on 13 or 14 vertices. The next example of a walk-regular graph that is neither vertex-transitive nor distance-regular appears to be given on 15 vertices. Here is its Graph6 code:

  • N]KOOHBO_GpH_KGQ?oW

The first example of a walk-regular graph that is neither vertex-transitive nor distance-regular on 15 vertices that I have found appears to be the only quartic walk-regular graph of this kind on 15 vertices (up to isomorphism). However, I’ve currently yet to finish exhaustively searching for walk-regular graphs that are of valency 5 or greater on 15 vertices due to the apparent complexity of doing so; moreover I also haven’t finished exhaustively searching for walk-regular graphs of order greater than 15 due to running into the same apparent issues of complexity as well.

None of the distinct examples of walk-regular graphs that are neither vertex-transitive nor distance-regular on 12 or 15 vertices that I initially found were cubic: aside from the one on 15 vertices being quartic, the ones on 12 vertices that I have listed are quartic, 5-regular, 6-regular, and 7-regular respectively. This raised the question of whether or not it is possible to construct a cubic walk-regular graph that is neither vertex-transitive nor distance-regular. Fortunately, with the help of some pre-computed data about cubic graphs available on Gordon Royle’s homepage, I believe that I been able to successfully find a first example on 20 vertices. Here its Graph6 code:

  • SsP@@?OC?S@C@_@C?K?A_?AG?D??C_??]

I think it would be interesting to continue to search for more distinct examples of walk-regular graphs that are neither vertex-transitive nor distance-regular on, say, up to 30 vertices. However, without thinking of more insightful or efficient ways of constructing walk-regular graphs of this kind or determining under what conditions they can exist, it may be difficult to do so due to issues of complexity. I found that every one of the examples of walk-regular graphs that are neither vertex-transitive nor distance-regular presented here has an integral spectrum. I believe it is possible to take certain products of walk-regular graphs to construct a walk-regular graph that is neither vertex-transitve nor distance-regular on a larger number of vertices that does not have an integral spectrum. However, I find still find it odd that every one of the examples of that I have found so far, which I believe cannot be decomposed as a product of walk-regular graphs (with respect to the kinds of graph products that the class of walk-regular graphs is closed under), has had an integral spectrum. I’d wonder if it could possibly be true that walk-regular graphs that are neither vertex-transitive nor distance-regular will have an integral spectrum, assuming that they cannot be decomposed as a product of walk-regular graphs in this sense, or if something of that nature is true. Moreover, I’d wonder if it could be possibly be at least true that every cubic walk-regular graph that is neither vertex-transitive nor distance-regular has an integral spectrum, or if something of that nature is true as well. I think it would be useful to continue to search for more distinct examples of walk-regular graphs that are neither vertex-transitive nor distance-regular, and think of more systematic methods for constructing these kinds of examples, since e.g. there appears like there could still be more about the theory of walk-regular graphs still to be discovered.