9
$\begingroup$

Let $G$ and $H$ be two $r$-regular connected graphs of size $n$. Let $A$ be the set of permutations $P$ such that $PGP^{-1}=H$. If $G=H$ then $A$ is the set of automorphisms of $G$.

What is the best known upper-bound on the size of of $A$?
Are there any results for particular graph classes (not containing complete/cycle graphs)?

Note: Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the graph isomorphism problem. In fact, just counting the automorphisms is polynomial-time equivalent to graph isomorphism, c.f. R. Mathon, "A note on the graph isomorphism counting problem".

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

Wormald has shown that if $G$ is a connected $3$-regular graph with 2n vertices then the number of automorphisms of $G$ divides $3n\cdot 2^n$. In particular this gives a non-trivial exponential upper-bound for the $3$-regular case. Maybe there are results in this line for general $k$-regular graphs.

For a lower bound, consider formula $F$ with $n$ inputs whose gates are addition $\mod k$ gates of fan-in 2. Then using a resut of Toran one can construct a $k$-regular graph $G(F)$ with $O(k^2\cdot n)$ vertices whose automorphism group encodes all possible evaluations of $F$. This implies that the number of automorphisms of $G(F)$ is at least $k^n$. This shows that the there is an exponential lower bound for the number of automorphisms of $k$-regular graphs in function of its number of vertices.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Please consider the following graph , 1. $r_1$ regular graph and $r_2$ regular graph (none of them are complete or cycle graph) are joined with each others through E number of edges, say this joined graph is a irregular graph $G$ 2. each vertex of $r_1$ regular graph has edges with the $r_2$ regular graph. There is no two vertices of $r_1$ regular graph, that have same number of edges with $r_2$ regular graph. Can automorphism of G be exponential ? $\endgroup$
    – Michael
    Aug 4, 2015 at 18:40
  • 1
    $\begingroup$ yes. The graph G2 can have an exponential number of automorphisms. Let H1 be any r1 regular graph with n vertices, numbered 1...n.Let H2 be a graph that is obtained by the following process (divided into 3 comments). Let D be the diamond graph, i.e., a 4-cycle together with an edge connecting two previously non-adjacent vertices. Say that these two vertices are the internal vertices of D. The other two vertices are the external vertices of D. Clearly,there is an automorhpism which swaps both internal vertices and leaves the external vertices untouched. $\endgroup$
    – Mateus de Oliveira Oliveira
    Aug 5, 2015 at 15:11
  • 1
    $\begingroup$ Now, consider the disjoint union of two cycles C1 and C2 with n(n+1)/2 vertices numbered from 1 to n(n+1)/2. Also consider n(n+1)/2 copies of the diamod graph. Now for each i, connect one of the external vertieces of D_i to the i-th vertex of C1 and the other external vertex to the i-th vertex of C2. Then the graph H2 obtained by this process is 3-regular, and has an exponential number of automorhpisms, since the internal vertices of each D_i can be swapped separately. $\endgroup$
    – Mateus de Oliveira Oliveira
    Aug 5, 2015 at 15:12
  • 1
    $\begingroup$ Now for each vertex v_j of H1 we add 2j edges from v_j to internal vertices of diamonds in such a way that both internal vertices of a diamond D_i get connected to the same vertex in H1. This guarantees that the internal vertices of the diamond can still be swapped, and therefore the total number of automorphisms in the graph G2 is exponential. $\endgroup$
    – Mateus de Oliveira Oliveira
    Aug 5, 2015 at 15:12
  • $\begingroup$ It is easy to show that a connected graph of order $n$ and of maximum valency $k$ has automorphism group of order at most $nk(k-1)^{n-2}$. Find an ordering of the vertices such that, starting with the second one, each vertex is adjacent to at least one vertex that came before. Let $G_i$ be the subgroup fixing the first $i$ vertices. This is a descending chain of subgroups, with $|G:G_1|\leq n$ and $G_n=1$. It follow by the orbit-stabiliser theorem that $|G_1:G_2|\leq k$, and $|G_i:G_{i+1}|\leq k-1$ for $i\in\{2,\ldots,n-1\}$. $\endgroup$
    – verret
    Oct 25, 2017 at 23:16
5
$\begingroup$

If you allow the graphs to be disconnected, then there are no good upper bounds, with respect to the number of vertices.

For $r$-regular graphs take the disjoint union of $l$ complete graphs $K_{r+1}$. Then the graph has $(r+1)\cdot l$ vertices, and $(r+1)!\cdot l!$ automorphisms.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.