7
$\begingroup$

I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive.

I am also interested in knowing if this problem is in P, NP, NPC or some other interesting facts about its complexity class.

$\endgroup$
3
$\begingroup$

If you had an oracle from Graph Isomorphism, then for constant $t$ you can check whether a graph is $t$-transitive. For example, to check if a graph is $1$-transitive, for every vertex $i$ create a variant $G_i$ of your original graph by attaching an "appendage" at vertex $i$, say a very long path or a very large star. The graph is transitive if all $G_i,G_j$ are isomorphic.

$\endgroup$

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.