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

<p>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. </p>

CC BY-SA 3.0
2015-08-01T16:26:19.063Z
2015-08-01T17:37:43.807Z
2015-08-01T17:37:43.807Z
tori
<p><a href="http://www.jstor.org/stable/2043017?seq=1#page_scan_tab_contents">Wormald</a> 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.</p>

<p>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 <a href="http://epubs.siam.org/action/showAbstract?page=1093&amp;volume=33&amp;issue=5&amp;journalCode=smjcat&amp;isAuthorized=no">Toran</a> 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. </p>

CC BY-SA 3.0
2015-08-04T18:40:10.497Z
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 ?
Michael
CC BY-SA 3.0
2015-08-05T15:11:32.640Z
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.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-08-05T15:12:09.457Z
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.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2015-08-05T15:12:30.323Z
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.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2017-10-25T23:16:52.557Z
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\}$.
verret
CC BY-SA 3.0
2015-08-01T18:16:18.587Z
2015-08-01T18:23:28.217Z
2015-08-01T18:23:28.217Z
Mateus de Oliveira Oliveira
<p>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$.</p>

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

<hr>

<p>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".</p>

<reference-request><graph-theory><co.combinatorics><graph-isomorphism><gr.group-theory>
Number of Automorphisms of a graph for graph isomorphism
Michael
# Number of Automorphisms of a graph for graph isomorphism

(Asked by: username_0 on 2015-08-01)

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

**Tags:** reference-request, graph-theory, co.combinatorics, graph-isomorphism, gr.group-theory


---

## 2 answers

### Answer by username_2 on 2015-08-01. Score: 9 | Accepted answer

[Wormald](http://www.jstor.org/stable/2043017?seq=1#page_scan_tab_contents) 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](http://epubs.siam.org/action/showAbstract?page=1093&volume=33&issue=5&journalCode=smjcat&isAuthorized=no) 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.

> **Comments:**
> **username_0**: 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 ?  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_3**: 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\}$.  

---

### Answer by username_1 on 2015-08-01. Score: 5

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.


---

