Let $A$ be the adjacency matrix of an $r$-regular graph $G$ with $n$ vertices (Not complete or cycle graph) . Also, let $Aut(G)$ be the set of all its automorphisms (i.e. set of permutation matrices).
So, if $P_k \in Aut(G)$, then $P_k A P_k^{-1}=A$. Suppose the order of the group generated by a single element $P_k$ ( i.e $\langle P_k\rangle$ ) is $m_k$.
Does there always exist an unique $P_k$(except identity) of an unique order $O(n^k)$ where $k$ is a constant?
Does there always exist a polynomial size set of permutation matrices, which is a subset of $Aut(G)$ ,where each permutation $P_k$ , has order $n^l$ where $l$ is a constant?
In Strongly Regular Graph, Every automorphism has order at most $O(n^8)$. Does there exist a polynomial size(i.e set size is at most $O(n^t)$) set where each element has order $n^l$ where $l$ is a constant?
Can the automorphism set $Aut(G)$ be divided in to classes based on a certain “property” ( e.g. order of the group generated by single automorphism or eigenvalue etc) ?
[ For example, if every automorphism has different order then one can divide $Aut(G)$ in to total $|Aut(G)|$ sets/classes. If elements of $Aut(G)$ have 2 order then $Aut(G)$ can be divided into 2 classes . This kind of classification is based on order . It could be based on something else. ]
If (1),(2),(3) are not possible in general, is there a certain class of graph which follow any (1),(2),(3)?
For Strongly regular graph,there is an upper bound on the order of automorphism (see László Babai).
Motivation: A graph isomorphism algorithm needs to find 'compatible' set of automorphism. In an attempt, to decrease the number of possible candidates , above questions are asked.
This post is partially motivated by this query .
