Graph Isomorphism Algorithm of Vertex Transitive Graphs and other.

Question

What are the best known Graph-Isomorphism algorithms for below graph classes-

1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive.

Provide run-times/time complexity of algorithm, if possible.

Also, If a graph has large number of automorphisms like above graphs, is it helpful to determine isomorphism? Is there any such relationship in current literature ?

Answer 1

Graph Isomorphism of Vertex Transistive Graphs is GI Complete(Graph-Isomorphism Complete) .

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. So, if vertex-transitivity test can be done in polynomial time, then so is isomorphism test for vertex-transitive graphs (there exists a polynomial time reduction). This is because two vertex-transitive graphs are isomorphic if and only if their disjoint union is vertex-transitive, thus computational complexity of graph isomorphism for vertex-transitive graphs lies in the same class of graph isomorphism .

See a related paper by Jajcay, Malnič, Marušič [1] , it says -

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.

So, saying a graph is vertex transitive gives no extra information, benefits to test isomorphism. One has to find out the automorphism set of the Vertex Transistive Graph . Determining a generating set for automorphism group of a given graph is GI Complete (Due to Rudi Mathon [2]), it means that the determining the a generating set for automorphism group of a given graph is equal to solving graph isomorphism problem .

Same argument could be used to edge-transitive, arc-transitive (or symmetric) , distance-transitive graph.

Addition:

1.

Thank you very much for your edit. Your reduction from VT to Iso is elegant and can be improved to a many-one reduction: simply ask for graph isomorphism, once, of the disjoint union of all the copies. Next, you provide a reduction from VTIso (vertex transitive graph isomorphism) to VT, so we now know that $VTIso \leq VT \leq Iso$. Does the reverse, $Iso \leq VTIso$, hold? I tried finding a reduction for $Iso\leq VTIso$ and for $VT\leq Aut$, but failed.

• from comment of Lieuwe Vinkhuijzen .

---

1. 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][JMM07]

2. Mathon, Rudolf (1979), "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (3): 131–132, doi:10.1016/0020-0190(79)90004-8