login
A058890
Smallest number of nodes in a graph whose automorphism group is cyclic of order n.
1
0, 2, 9, 10, 15, 11, 14, 14, 15, 17, 22, 18, 26, 16, 21, 22, 34, 17, 38, 25, 23, 24, 46, 22, 35, 28, 33, 24, 58, 23, 62, 38, 31, 36, 29, 24, 74, 40, 35, 29, 82, 25, 86, 32, 27, 48, 94, 30
OFFSET
1,2
COMMENTS
Given a(n), a(m), where gcd(n,m)=1, the disjoint union of the two corresponding graphs has cyclic automorphism group of order n*m, so a(n*m) <= a(n) + a(m). In most cases, this is an equality, with some corrections described in the formula. - Mikhail Lavrov, Nov 05 2022
REFERENCES
William C. Arlinghaus, The classification of minimal graphs with given Abelian automorphism group, Memoirs of the American Mathematical Society, Number 330, September 1985.
F. Harary, Graph Theory, Page 176, Problem 14.7.
FORMULA
a(2) = 2; for r > 1, a(2^r) = 2^r + 6; for p = 3 or 5 and r > 0, a(p^r) = p^r + 2p; for p prime >= 7 and r > 0, a(p^r) = p^r + p. (Harary)
a(n) = a(p1^r1 p2^r2 ... pk^rk) = a(p1^r1) + ... + a(pn^rn) - F where F is a "correction factor" which depends on the exponents of the primes 2, 3 and 5 in the prime factorization of the number n. Call these values n2, n3 and n5 respectively.
The correction factor F is 0 if n3 = 0 (so unless 3 divides n, the upper bound is exact); 4 if n2 = 2, n3 >= 1 and n5 = 1; 3 if n2 != 2, n3 >=1 and n5 = 1; 1 if n2 = 2, n3 >= 1 and n5 != 1; 1 if n2 >= 2, n3 = 1 and n5 != 1; 0 otherwise.
EXAMPLE
a(3)=9 since the smallest graph with automorphism group C_3 is the graph with 9 nodes linked as "Smallest Cyclic Group Graph" on House of Graphs. Similarly, a(4)=10 since the smallest graph with automorphism group C_4 is the graph linked as "Smallest C4 Graph". - Mikhail Lavrov, Nov 05 2022
MATHEMATICA
a[1] = 0; a[2] = 2; a[n_ /; IntegerQ[ Log[2, n]]] := 2^Log[2, n] + 6; a[n_ /; IntegerQ[ Log[3, n]]] := 3^Log[3, n] + 6; a[n_ /; IntegerQ[ Log[5, n]]] := 5^Log[5, n] + 10; a[n_ /; MatchQ[ FactorInteger[n], {{(p_)^(r_)} /; PrimeQ[p]}]] := p^r + 2*p; a[(n_)?PrimeQ] := 2*n; a[n_] := a[n] = (fi = FactorInteger[n]; n2 = (s = Select[fi, First[#] == 2 &, 1]; If[s == {}, 0, s[[1, 2]]]); n3 = (s = Select[fi, First[#] == 3 &, 1]; If[s == {}, 0, s[[1, 2]]]); n5 = (s = Select[fi, First[#] == 5 &, 1]; If[s == {}, 0, s[[1, 2]]]); pp = fi[[All, 1]]; rr = fi[[All, 2]]; Total[a /@ (pp^rr)] - cf[n2, n3, n5]); cf[n2_, 0, n5_] = 0; cf[2, n3_ /; n3 >= 1, 1] = 4; cf[n2_ /; n2 != 2, n3_ /; n3 >= 1, 1] = 3; cf[2, n3_ /; n3 >= 1, n5_ /; n5 != 1] = 1; cf[n2_ /; n2 >= 2, 1, n5_ /; n5 != 1] = 1; cf[_, _, _] = 0; Table[a[n], {n, 1, 48}] (* Jean-François Alcover, Oct 19 2011 *)
CROSSREFS
Cf. A080803.
Sequence in context: A344145 A051017 A078180 * A369205 A306998 A047468
KEYWORD
nonn,nice,easy
AUTHOR
N. J. A. Sloane, Jan 08 2001
EXTENSIONS
Additional comments and more terms from David Wasserman and Gordon F. Royle, Jun 09 2002
STATUS
approved