|
%I #16 Dec 07 2022 09:11:43
%S 0,2,9,10,15,11,14,14,15,17,22,18,26,16,21,22,34,17,38,25,23,24,46,22,
%T 35,28,33,24,58,23,62,38,31,36,29,24,74,40,35,29,82,25,86,32,27,48,94,
%U 30
%N Smallest number of nodes in a graph whose automorphism group is cyclic of order n.
%C 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
%D William C. Arlinghaus, The classification of minimal graphs with given Abelian automorphism group, Memoirs of the American Mathematical Society, Number 330, September 1985.
%D F. Harary, Graph Theory, Page 176, Problem 14.7.
%H House of Graphs, <a href="https://houseofgraphs.org/graphs/1315">Smallest Cyclic Group Graph</a>
%H House of Graphs, <a href="https://houseofgraphs.org/graphs/49350">Smallest C4 Graph</a>
%F 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)
%F 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.
%F 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.
%e 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
%t 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 *)
%Y Cf. A080803.
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_, Jan 08 2001
%E Additional comments and more terms from _David Wasserman_ and _Gordon F. Royle_, Jun 09 2002
|
