Graph Isomorphism Algorithm of Vertex Transitive Graphs and other.

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 ?

• Questions older than 60 days cannot be migrated. You can re-ask it (but give a link to this question if you do). Oct 28 '16 at 14:47

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.

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

• Can you provide a reference for the claim that generating a graph's automorphism group is equivalent to solving graph isomorphism in the case where both graphs are known to be vertex transitive? I cannot find Mathon's result on Google scholar, and even if I could, the fact that in general finding the automorphism group is GI Complete does not mean that this is also true for the case of vertex-transitive graphs. Oct 21 '16 at 12:37
• 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? This is what we are looking for when we ask whether VTIso is GI-Complete. I tried finding a reduction for $Iso\leq VTIso$ and for $VT\leq Aut$, but failed. Oct 27 '16 at 22:40
• You appended my comment to your answer, but did not answer the question whether graph isomorphism reduces to graph isomorphism to vertex-transitive graphs. Also, this question and answer look much more at home at cs.stackexchange or cstheory.stackexchange, but I don't have the power to migrate it. Oct 28 '16 at 14:36
• @LieuweVinkhuijzen , I have asked it on CST ME : cstheory.stackexchange.com/questions/36878/… Oct 28 '16 at 14:59