what are known bounds on complexity of nontrivial graph automorphism
Determining if a graph has a nontrivial automorphism Cook-reduces (polynomial time Turing) to Graph Isomorphism (determine if a pair of graphs is isomorphic) (exercise for the reader).  It is not known to be equivalent to graph isomorphism.

In turn, graph isomorphism can be solved in $2^{\tilde O(\sqrt{n})}$ time and lies in $NP \cap coAM$.  In particular, it is not $NP$-complete unless the polynomial hierarchy collapses.