<p>I don't have a complete answer, but I think both problems are open.</p>

<hr>

<p>The paper by Jajcay, Malni&#x10D;, Maru&scaron;i&#x10D; [3] is related to your first question.
They provide some tools to test vertex-transitivity. They say in the introduction that:</p>

<blockquote>
  <p>For a given finite graph $\Gamma$,
  it is decidedly hard to determine whether $\Gamma$ is vertex-transitive,
  and the ultimate answer comes usually only after a substantial part of
  the full automorphism group of $\Gamma$ has been determined.</p>
</blockquote>

<p>Note that vertex-transitivity test can be done by testing graph isomorphism $n−1$ times.
Make two copies $G$ and $G'$ of your graph,
with special anchors (like paths of length $n+1$) at $u \in V(G)$ and $v \in V(G')$.
There is an isomorphism between $G$ and $G'$ if and only if
the original graph has an automorphism mapping $u$ to $v$.
Thus you can test vertex-tansitivity by fixing a vertex $x$,
and checking that there are automorphisms mapping $x$ to all the other vertices.</p>

<p>Also note that if vertex-transitivity test can be done in polynomial time,
then so is isomorphism test for vertex-transitive graphs.
This is because two vertex-transitive graphs are isomorphic if and only if
their disjoint union is vertex-transitive.
I believe that complexity of graph isomorphism for vertex-transitive graphs is not known.</p>

<hr>

<p>For the 2nd question, I found a partial result.
A <em>circulant graph</em> is a Cayley graph on a cyclic group.
Evdokimov and Ponomarenko [2] show that recognition of
circulant graphs can be done in polynomial time.
Also the book chapter by Alspach [1, Chapter 6: Cayley graphs, Section 6.2: Recognition]
would be interesting for you, although it says that:</p>

<blockquote>
  <p>We shall ignore the computational problem of recognizing whether an
  arbitrary graph is a Cayley graph. Instead, we always assume that
  Cayley graphs have been described in terms of the groups on which they
  are built, together with the connection sets. For most problems this
  is not a drawback.</p>
</blockquote>

<hr>

<ol>
<li>Beineke, Wilson, Cameron. <a href="http://books.google.co.jp/books?id=z2K26gZLC1MC&amp;pg=PA156">Topics in Algebraic Graph Theory</a>. Cambridge University Press, 2004. </li>
<li>Evdokimov, Ponomarenko. Circulant graphs: Recognizing and isomorphism testing in polynomial time. St. Petersburg Math. J. 15 (2004) 813-835. <a href="http://dx.doi.org/10.1090/S1061-0022-04-00833-7">doi:10.1090/S1061-0022-04-00833-7</a></li>
<li>Jajcay, Malni&#x10D;, Maru&scaron;i&#x10D;. On the number of closed walks in vertex-transitive graphs. Discrete Math. 307 (2007) 484-493. <a href="http://dx.doi.org/10.1016/j.disc.2005.09.039">doi:10.1016/j.disc.2005.09.039</a></li>
</ol>

CC BY-SA 3.0
2012-10-29T01:27:34.513Z
In fact, vertex-transitivity can be tested using $n-1$ graph isomorphism tests: fix a vertex $x$, and check that there is an automorphism sending $x$ to any other vertex.
Yuval Filmus
CC BY-SA 3.0
2012-10-28T23:48:57.507Z
2012-10-29T06:12:29.367Z
2012-10-29T06:12:29.367Z
Yota Otachi
<p>I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.</p>

<blockquote>
  <p><strong>Question 1.</strong> Let $G$ be a simple undirected graph of order $n$. What is the
  computational complexity (in terms of $n$) of determining if $G$ is
  vertex-transitive?</p>
</blockquote>

<p>Recall that a graph $G$ is <em>vertex-transitive</em> if $\mathrm{Aut}(G)$ acts transitively on $V(G).$ </p>

<p>I am not sure if the above definition allows for a polynomial time algorithm since it can be that the order of $\mathrm{Aut}(G)$ is exponential.</p>

<p>However vertex-transitive graphs have some other structural properties that might be exploited in order to be able to efficiently determine them so I am not sure what is the status of the above question.</p>

<p>Another interesting subclass of vertex-transitive graphs that has even more structure is the class of <a href="http://en.wikipedia.org/wiki/Cayley_graph">Cayley</a> graphs. So it is natural to also pose the following related question</p>

<blockquote>
  <p><strong>Question 2.</strong> What is the computational complexity of determing if a graph $G$ is a
  Cayley graph?</p>
</blockquote>

CC BY-SA 3.0
2012-10-29T05:46:40.203Z
Even though the automorphism group can be super-exponential, I think it can be represented in polynomial space because the minimum number of generators is at most logarithmic in $|\textrm{Aut}(G)|$
Timothy Sun
CC BY-SA 3.0
2012-10-29T17:55:21.550Z
Note that every vertex-transitive graph is a Cayley-Schrier graph: there is some group $G$ with generating set $S$ and subgroup $H$ such that the vertices of the graph are the cosets $G/H$, and two cosets are linked by an edge if some element of $S$ takes one to the other.
Joshua Grochow
CC BY-SA 3.0
2018-03-21T18:28:43.143Z
Related: https://mathoverflow.net/questions/156947/vertex-transitive-and-cayley-graphs
Peter Heinig
<cc.complexity-theory><graph-theory><gr.group-theory>
Complexity of recognizing vertex-transitive graphs
Jernej
# Complexity of recognizing vertex-transitive graphs

(Asked by: username_0 on 2012-10-27)

I am not knowledgeable in the area of complexity theory involving groups so I apologize if this is a well known result.

> **Question 1.** Let $G$ be a simple undirected graph of order $n$. What is the
> computational complexity (in terms of $n$) of determining if $G$ is
> vertex-transitive?

Recall that a graph $G$ is *vertex-transitive* if $\mathrm{Aut}(G)$ acts transitively on $V(G).$

I am not sure if the above definition allows for a polynomial time algorithm since it can be that the order of $\mathrm{Aut}(G)$ is exponential.

However vertex-transitive graphs have some other structural properties that might be exploited in order to be able to efficiently determine them so I am not sure what is the status of the above question.

Another interesting subclass of vertex-transitive graphs that has even more structure is the class of [Cayley](http://en.wikipedia.org/wiki/Cayley_graph) graphs. So it is natural to also pose the following related question

> **Question 2.** What is the computational complexity of determing if a graph $G$ is a
> Cayley graph?

**Tags:** cc.complexity-theory, graph-theory, gr.group-theory
> **Comments:**
> **username_1**: Even though the automorphism group can be super-exponential, I think it can be represented in polynomial space because the minimum number of generators is at most logarithmic in $|\textrm{Aut}(G)|$  
> **username_2**: Note that every vertex-transitive graph is a Cayley-Schrier graph: there is some group $G$ with generating set $S$ and subgroup $H$ such that the vertices of the graph are the cosets $G/H$, and two cosets are linked by an edge if some element of $S$ takes one to the other.  
> **username_3**: Related: https://mathoverflow.net/questions/156947/vertex-transitive-and-cayley-graphs  

---

## 1 answers

### Answer by username_4 on 2012-10-28. Score: 14 | Accepted answer

I don't have a complete answer, but I think both problems are open.

---

The paper by Jajcay, Malnič, Marušič [3] is related to your first question.
They provide some tools to test vertex-transitivity. They say in the introduction that:

> For a given finite graph $\Gamma$,
> it is decidedly hard to determine whether $\Gamma$ is vertex-transitive,
> and the ultimate answer comes usually only after a substantial part of
> the full automorphism group of $\Gamma$ has been determined.

Note that vertex-transitivity test can be done by testing graph isomorphism $n−1$ times.
Make two copies $G$ and $G'$ of your graph,
with special anchors (like paths of length $n+1$) at $u \in V(G)$ and $v \in V(G')$.
There is an isomorphism between $G$ and $G'$ if and only if
the original graph has an automorphism mapping $u$ to $v$.
Thus you can test vertex-tansitivity by fixing a vertex $x$,
and checking that there are automorphisms mapping $x$ to all the other vertices.

Also note that if vertex-transitivity test can be done in polynomial time,
then so is isomorphism test for vertex-transitive graphs.
This is because two vertex-transitive graphs are isomorphic if and only if
their disjoint union is vertex-transitive.
I believe that complexity of graph isomorphism for vertex-transitive graphs is not known.

---

For the 2nd question, I found a partial result.
A *circulant graph* is a Cayley graph on a cyclic group.
Evdokimov and Ponomarenko [2] show that recognition of
circulant graphs can be done in polynomial time.
Also the book chapter by Alspach [1, Chapter 6: Cayley graphs, Section 6.2: Recognition]
would be interesting for you, although it says that:

> We shall ignore the computational problem of recognizing whether an
> arbitrary graph is a Cayley graph. Instead, we always assume that
> Cayley graphs have been described in terms of the groups on which they
> are built, together with the connection sets. For most problems this
> is not a drawback.

---

1. Beineke, Wilson, Cameron. [Topics in Algebraic Graph Theory](http://books.google.co.jp/books?id=z2K26gZLC1MC&pg=PA156). Cambridge University Press, 2004.
2. Evdokimov, Ponomarenko. Circulant graphs: Recognizing and isomorphism testing in polynomial time. St. Petersburg Math. J. 15 (2004) 813-835. [doi:10.1090/S1061-0022-04-00833-7](http://dx.doi.org/10.1090/S1061-0022-04-00833-7)
3. Jajcay, Malnič, Marušič. On the number of closed walks in vertex-transitive graphs. Discrete Math. 307 (2007) 484-493. [doi:10.1016/j.disc.2005.09.039](http://dx.doi.org/10.1016/j.disc.2005.09.039)

> **Comments:**
> **username_5**: In fact, vertex-transitivity can be tested using $n-1$ graph isomorphism tests: fix a vertex $x$, and check that there is an automorphism sending $x$ to any other vertex.  

---

