Graphs with automorphism groups of given order

[Gordon Royle]

> %S A000001 0, 2, 9, 4, 15, 3, 14, 4, 15, 5, 22, 5, 26, 7, 21, 6, 34, 9, 38,
>            7, 23, 11, 46, 4, 30, 13, 24, 9, 58, 14, 62
> %N A000001 The number of vertices of the minimal graph with automorphism
>            group of order n
> %C A000001 Most terms were found in the thread "Automorphismengruppen von
>            Graphen" in the German newsgroup "de.sci.mathematik" (mostly by
>            Hauke Klein).
>            The terms a(9)=15, a(15)=21, a(21)=23, a(27)=24, a(30)=14 still
>            need verification.
> %e A000001 a(4)=4 because the graph with 4 vertices and exactly one edge has
>            an automorphism group of order 4 and no smaller graph has exactly
>            4 automorphisms.
> %O A000001 1
> %K A000001 ,more,nice,nonn,
> 
> Is somebody able to verify the terms mentioned in the comment? The numbers
> given are upper bounds, and I believe they cannot be improved.


Do you want the good news or the bad news first?

Good: a(15) = 21 is definitely true - there is only one group of order
15 and so the known results for cyclic groups give the answer of 21.

Bad: a(21) != 23

The number you have given is the smallest size of a graph with a 
*cyclic* automorphism group, but there are other groups (well, one other
group) and therefore potentially other graphs...

Take 3 7-sets {a_0,...a_6}, {b_0,..b_6}, {c_0,...c_6} and the following
edges

	a_0 joined to b_0,c_0 and {a_3,a_4,b_2,b_3,c_1,c_3}
	b_0 joined to a_0,c_0 and {a_4,a_5,b_2,b_5,c_1,c_5}
	c_0 joined to a_0,b_0 and {a_4,a_6,b_2,b_6,c_1,c_6}

and map the subscripts in a cycle of order 7.

This is an 8-regular graph with automorphism group of order 21...

So a(21) <= 21.

Cheers

-- 
Dr. Gordon F Royle, http://www.csse.uwa.edu.au/~gordon, gordon at csse.uwa.edu.au
--