A058890

[David Wasserman]

%I A058890
%S A058890 1,2,9,10,15
%N A058890 Smallest number of nodes in a graph whose group is cyclic 
of order n.
%D A058890 F. Harary, Graph Theory, Page 176, Problem 14.7.
%K A058890 nonn,easy,nice,more
%O A058890 1,2
%A A058890 njas, Jan 08 2001

I looked up the reference.  The group referred to is the graph's automorphism
group.  Harary states (and the proof is the exercise)

(a) a(2) = 2; for r > 1 a(2^r) = 2^r + 6;
 
(b) for p = 3 or 5, and r > 0, a(p^r) = p^r + 2p;

(c) for p prime and >= 7, and r > 0, a(p^r) = p^r + p.

Harary also says that a(n) can be computed for non-prime-power n, but the
formula is complicated.

I don't think this sequence should be labelled 'easy'.  We can easily compute a
large number of terms from Harary's formulas, but there seems to be no easy way
to compute the next term.  (I don't think there's a feasible algorithm to
compute the automorphism group of a graph.)

I've figured out how to prove (c).  Having constructed the required graph, one
must show that no smaller number of elements suffices.  If the graph has an
automorphism of order p^r, it must have an orbit with p^r elements.  One can
show that if this orbit has cyclic symmetry, it must also have dihedral
symmetry, and that the extra symmetry can't be broken (while maintaining the
cyclic symmetry) by adding any number of single-element orbits.  So there must
be another orbit with more than one element, which means at least p more
elements.

I assume (b) can be done similarly, but it is harder, because one 
must show that
a single p-element orbit isn't enough.  (a) looks even harder.  But in the case
when n is not a prime power, then it's no longer necessary to have an n-element
orbit, so I don't see any way to get a handle on the problem.

There is an easy way to get an upper bound.  If p and q are distinct primes,
then by placing side by side the graphs for p^i and q^j, we get a graph whose
group is cyclic of order p^i*q^j.  So a(p^i*q^j) <= a(p^i) + a(q^j), and
similarly for more than two primes.  This seems hard to beat.  However, if this
inequality were always an equality, I think Harary would have said so; it's not
so hard to write
(d) a(p_1^r_1*...*p_n^r_n) = a(p_1^r_1) + ... + a(p_n^r_n),
and I would not call this a complicated formula.

So here's 80 terms; the ones in parentheses are my upper bounds, and the rest
are from Harary:
1, 2, 9, 10, 15, (11), 14, 14, 15, (17), 22, (19), 26, (16), (24), 
22, 34, (17),
38, (25), (16), (24), 46, (23), 35, (28), 33, (24), 58, (26), 62, 38, (31),
(36), (29), (25), 74, (40), (35), (29), 82, (25), 86, (32), (30), (48), 94,
(31), 56, (37), 102, (36), 106, (35), (37), (28), (47), (60), 118, (34), 122,
(64), (29), 70, (41), (33), 134, (44), (55), (31), 142, (29), 146, (76), (44),
(48), (36), (37), 158, (37).