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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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.