A graph $G=(V,E)$ is arc-transitive if its symmetry group acts transitively on ordered pairs of adjacent vertices.

In general, the complement of an arc-transitive graph is not arc-transitive. But I have a hard time finding an example of such a graph if I assume $\mathrm{diam}(G)=\max_{v,w\in V} \mathrm{dist}(v,w)=2$. All my examples of diameter 2 arc-transitive graphs have arc-transitive complements: e.g.

  • the 4-cycle and 5-cycle,
  • the Petersen-graph,
  • the Hoffman-Singleton graph,
  • the Payley graphs,
  • ...

I suppose an equivalent question would be: find a diameter 2 arc-transitive graph that is not distance-transitive.


Complements don't even have to be edge transitive. Perhaps the simplest example is the wreath graph $W_5$ (which is obtained by applying the construction below to $C_5$).

Call two vertices "twins", if they have the same neighbourhood in $G$. Since the twin-relation is preserved under automorphisms, it suffices to construct an arc-transitive graph $G$ of diameter $2$ which has non-adjacent twins as well as non-adjacent non-twins.

Now let $G$ be an arc-transitive graph $G$ of diameter $2$ and assume that there are non-adjacent non-twins $v_1$ and $v_2$ in $G$. Take the lexicographic product of $G$ with an empty graph on $2$ vertices. In other words, we add a twin $v'$ to every vertex $v$ of $G$, where $v'$ is connected to all neighbours of $v$ and their respective twins. The resulting graph is still arc transitive, has diameter $2$, and contains non-adjacent twins $v$ and $v'$ as well as non-adjacent non-twins $v_1$ and $v_2$.


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.