Minimal graphs for groups

[franktaw at netscape.net]

A080803 (the size of the smallest graph whose symmetry group has n 
elements) and A058890 (the size of the smallest graph whose symmetry 
group is cyclic of order n) are closely related.  It seems to me that 
they should have cross-references to each other:

%Y A080803 Cf. A058890.

%Y A058890 Cf. A080803.

They should also have the same value for a(1), since the cyclic group 
is the only group of order 1.  In particular, I think A058890(1) should 
be 0.

-----
It also occurs to me to wonder about the equivalents of these sequences 
for digraphs.  One can always get a digraph on n nodes whose symmetry 
group is C_n by just connecting them in a cycle.  I think this means 
that the digraph equivalent of A058890 is actually A008457 (sum of 
unitary prime power divisors).

For the equivalent of A080803, A001414 is an upper bound.  Given a set 
of digraphs D_i whose symmetry groups have order k_i, one can construct 
a digraph on the union whose order is Product k_i.  Since the 
complement of a disconnected graph is connected, and the complement of 
a graph (or digraph) has the same symmetry group, we can take all the 
D_i to be connected.  Now if there are two isomorphic components, 
combine them into one by adding an arrow from each point in one to each 
point in the other; repeat as necessary.  Once all components are 
distinct, the symmetry group of the disjoint union will be the direct 
product of the symmetry groups of the D_i's.

A001414 is not exact, however; in particular, a(6) = 3, while 
A001414(6) = 5.

I think we start:
0,2,3,4,5,3,7,4,6,7,11,7,13,9,8,6,17,6,19,9,10,13,23,4

Franklin T. Adams-Watters

________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.