|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
