5
$\begingroup$

Suppose I gave you a finite graph, and asked you whether it was vertex-transitive. How hard is that algorithmically?

The second question is: suppose I gave you a vertex transitive finite graph, and asked you whether it was a Cayley graph. How hard is that?

Improve this question
$\endgroup$
11
  • 4
    $\begingroup$ This question seems relevant: cstheory.stackexchange.com/questions/14106/… $\endgroup$
    – Arnaud
    Feb 7, 2014 at 14:14
  • $\begingroup$ @Arnaud: "relevant" is putting it mildly, it seems essentially identical, BUT even though there is an accepted answer, the question is not answered in any substantial way. Maybe the moderators can weigh in on what the right thing is... $\endgroup$
    – Igor Rivin
    Feb 7, 2014 at 15:24
  • $\begingroup$ Is there any reason to expect that this would be easier than the general graph automorphism/isomorphism problem? $\endgroup$
    – Derek Holt
    Feb 7, 2014 at 17:51
  • $\begingroup$ @DerekHolt Vertex transitive graphs have a lot of extra structure, so certainly on a heuristic level one might think that if the answer is "no" (to vertex transitivity), then there would be some easy spectral (say) certificate. Also, one might ask: if all the degree sequences are equal, then is the graph vertex transitive (I assume the answer is "no", but one probably has to wake up pretty early in the morning to find a counterexample...) $\endgroup$
    – Igor Rivin
    Feb 7, 2014 at 18:53
  • 2
    $\begingroup$ I would be totally astonished if there was a better way of detecting vertex-transitivity than computing the automorphism group of the graph. All attempts at finding spectral or other combinatorial invariants that can distinguish graphs with big groups from the others have foundered, usually in the murky waters of strongly regular graphs where all the graphs "look the same" but have wildly different groups. $\endgroup$
    – Gordon Royle
    Feb 8, 2014 at 0:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.