4
$\begingroup$

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:

qqq

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?

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Erick Wong Jul 26 '15 at 15:05
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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