# Is there an efficient way to iterate vertex-transitive graphs?

For fixed number of vertices $n$, I want to iterate through all vertex-transitive simple graphs to check for some properties. A nice way to find vertex-transitive graphs is to iterate binary vectors $\vec v \in \{0;1\}^n$ and for each vector $\vec v$ obtain a "nice" adjacency matrix by right-shifting the indices in row $i$ by $i-1$ like so:

$$M = \begin{bmatrix} v_{1} & v_{2} & \dots & \cdots & v_{n} \\ v_{n} & v_1 & v_2 & \dots & v_{n-1} \\ \dots & \dots & \dots & \dots & \dots \\ v_2 & v_3 & \dots & v_{n} & v_1\\ \end{bmatrix}$$

This will yield a simple undirected graph if $\vec v$ is of the form $(0,a_1,a_2,..,a_k,a_{k-1},..,a_1)$. Of course a lot of the graphs are isomorphic, but I am not too worried about that (unless anyone has an idea on how to improve on that).

However, it seems that not all vertex-transitive graphs have such a nice representation. For instance on 8 vertices, with degree 3, the only good vectors (by the above restriction) are $(0,1,0,0,1,0,0,1), (0,0,1,0,1,0,1,0)$ and $(0,0,0,1,1,1,0,0)$. None of these correspond to the following graph:

How can I find the remaining graphs, and is there an understandable property that divides vertex-transitive graphs into these two groups? Does my iteration cover most or almost none of the vertex-transitive graphs?

• I don't have a good answer for your main question, but the graphs you're describing are called circulant graphs, which are a special case of Cayley graphs (which in turn are a special case of vertex-transitive graphs). The automorphism group of an arbitrary vertex-transitive graph might not contain a cycle (note: this is not the same as $\text{Aut}(G)$ being cyclic, only that it contains a subgroup acting cyclically on all vertices). – Erick Wong Jul 26 '15 at 15:05

## 1 Answer

Partial answer: If $n$ is prime, then every vertex-transitive graph with $n$ vertices is isomorphic to one of the form that you have given, because every transitive permutation group of prime degree $p$ contains a $p$-cycle. In general, the property that divides the vertex-transitive graphs into these two classes is whether the automorphism group of the graph contains an $n$-cycle or not.

For general $n$, the enumeration of vertex-transitive graphs is a challenging problem. It has been successfully carried out for $n\leq 31$ (see http://oeis.org/A006799). To address the question of whether your iteration covers "most or almost none", you can compare the number of circulant graphs (see https://oeis.org/A049287) with the number of vertex-transitive graphs for each $n$. From these tables, you can see that $n=8$ is the smallest $n$ for which these numbers differ -- 12 circulant graphs, versus 14 vertex-transitive graphs -- so your counterexample is the smallest possible (and the other counterexample for $n=8$ is just given by the complementary graph). On the other hand, for $n=24$, there are 1312 circulant graphs but 15506 vertex-transitive graphs. From the limited data available, one might conjecture that for smooth $n$, asympotically "almost none" of the vertex-transitive graphs are circulant.