Graphs with automorphism groups of given order

[Jens Voss]

"Ed Pegg" wrote:
> 
>   Can you send me pictures or descriptions of all of these
> graphs?
> 
>   I will clean up the pictures (to any extent required) and
> post them in the Mathworld encyclopedia.

Sure, here are descriptions of the graphs involved:

Let K_n, E_n and C_n denote the complete, empty resp. cycle graphs on n
vertices. For every graph G, let G' be the complement of G. Then the
following hold:

 (1) |K_n| = n and Aut(K_n) = S_n
 (2) |E_n| = n and Aut(E_n) = S_n
 (3) |C_n| = n and Aut(C_n) = D_(2n) (for n >= 3)
 (4) |K_2 + E_2| = 4 and Aut(K_n + E_n) = Z_2 x Z_2
 (5) |C_n + E_2| = n+2 and Aut(C_n + E_2) = D_(2n) x Z_2 (for n >= 3)

As corollaries, we get the upper bounds

 a(n!) <= n
 a(2n) <= n    (for n >= 3)
 a(4n) <= n+2  (for n >= 3)
 a(4)  <= 4

For the odd terms, we look at two constructions:

For n >= 3, let A_n be the graph with vertices {a_i, b_i, c_i | 0 <= i < n} and
edges {(a_i,a_(i+1)), (a_i,b_i), (a_i,c_i), (b_i,c_i), (c_i,a_(i+1)) | 0 <= i < n}
(where all indices are to be read modulo n).
To picture this: A_n is made up of an n-gon (a_0, ..., a_(n-1)) with a
rectangle drawn over each side plus one diagonal in each rectangle.

 (6) |A_n| = 3n and Aut(A_n) = Z_n

Now let m be a divisor of n. Let (A_n)/m the graph obtained from A_n by identifying
b_i with every b_j where i is congruent j modulo (n/m) and likewise for the c_i.
Then we have

 (7) |(A_n)/m| = n + 2n/m and Aut((A_n)/m) = Z_n if n > 4 and m < n

The other construction requires n >= 6. Let B_n be the graph with vertices
{a_i, b_i | 0 <= i < n} and edges
{(a_i,a_(i+1)), (a_i,b_(i-1)), (a_i,b_i), (a_i,b_(i+1)), (a_i,b_(i+3)) | 0 <= i < n}
(again all indices modulo n). Then the following can be shown:

 (8) |B_n| = 2n and Aut(B_n) = Z_n

Now we can give a list of upper bounds for the numbers submitted:

1:  |E_0|           = 0
2:  |E_2|           = 2
3:  |A_3|           = 9
4:  |K_2 + E_2|     = 4
5:  |A_5|           = 15
6:  |C_3|           = 3
7:  |B_7|           = 14
8:  |C_4|           = 4
9:  |(A_9)/3|       = 15
10: |C_5|           = 5
11: |B_11|          = 22
12: |C_3 + E_2|     = 5
13: |B_13|          = 26
14: |C_7|           = 7
15: |(A_15)/5|      = 21
16: |C_4 + E_2|     = 6
17: |B_17|          = 34
18: |C_9|           = 9
19: |B_19|          = 38
20: |C_5 + E_2|     = 7
21: |B_7 + A_3|     = 23
22: |C_11|          = 11
23: |B_23|          = 46
24: |E_4|           = 4
25: |A_5 + (A_5)'|  = 30
26: |C_13|          = 13
27: |(A_9)/3 + A_3| = 24
28: |C_7 + E_2|     = 9
29: |B_29|          = 58
30: |A_3 + C_5|     = 14
31: |B_31|          = 62

The proofs that these graphs provide in fact LEAST upper bounds are quite
tedious, and are left to the interested readers :)

Regards,
Jens