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$.

  1. Does there always exist an unique $P_k$(except identity) of an unique order $O(n^k)$ where $k$ is a constant?

  2. 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?

  3. 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. ]

  4. 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 .

  • $\begingroup$ @DerekHolt , please see the link of L. Babai, it says, " In particular, we show that the order of every automorphism is $O(n^8)$", I am asking for regular graph analogous to Strongly regular graph. $\endgroup$ – Jim Aug 7 '15 at 21:55
  • 1
    $\begingroup$ For question$(3)$, always you can partition the automorphism group of any graph in two sets; odd permutations and even permutations. $\endgroup$ – Shahrooz Janbaz Aug 7 '15 at 22:04
  • $\begingroup$ @ShahroozJanbaz , yes, but the problem is, when you have an exponential size of automorphism set, this kind of partition does not help much in decreasing complexity of an algorithm unless one of the set has non exponential size (always). $\endgroup$ – Jim Aug 7 '15 at 22:16
  • $\begingroup$ So, please say your motivation directly. Maybe, we can say more by knowing your actual idea. $\endgroup$ – Shahrooz Janbaz Aug 7 '15 at 22:23
  • 2
    $\begingroup$ The answer to 1 is no, unless you count the identity element being the unique element of order $1$. $\endgroup$ – Derek Holt Aug 8 '15 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.