|
|
A342357
|
|
Number of fundamentally different rainbow graceful labelings of graphs with n edges.
|
|
2
|
|
|
1, 2, 11, 125, 1469, 30970, 1424807, 25646168, 943532049, 66190291008, 1883023236995, 119209289551407, 8338590851427689, 366451025462807402, 25231464507361789935, 2996947275258886238380, 211289282287835811874277, 12680220578500976681544666, 1815313698001596651227722787
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Rainbow graceful labelings are also known as rho-labelings, as originally introduced by Rosa in 1967.
Equivalently, they are graceful labelings of the digraph obtained by replacing each edge by a pair of arcs in opposite directions.
Consider vertices numbered 0 to 2n. For 1 <= k <= n, add an edge between v_k and (v_k+k) mod q, where q = 2n+1. (Thus (2n+1)^n possibilities.) Two such graphs are considered equivalent under the following operations: (i) rename each v to (v+1) mod q; (ii) rename each v to (av) mod q, where a is relatively prime to q. The number of equivalence classes is a(n).
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming, forthcoming exercise in Section 7.2.2.3.
A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Dunod Paris (1967) 349-355.
|
|
LINKS
|
|
|
EXAMPLE
|
Each equivalence class has exactly one graph with v_1=0.
For n=3 the eleven classes of graphs 0v_2v_3 are: {000,011,015,050,054,065}, {001,002,024,041,063,064}, {003,026,031,034,046,062}, {004,061}, {005,013,021,044,052,060}, {006,014,030,035,051,066}, {010,055}, {012,020,022,043,045,053}, {016,025,032,033,040,056}, {023,042}, {036}.
|
|
MATHEMATICA
|
sols[alf_, bet_, q_]:=Block[{d=GCD[alf, q]}, If[Mod[bet, d]!=0, 0, d]]
(* that many solutions to alf x == bet (modulo q) for 0<=x<q *)
f[l_, a_, b_, q_]:=Block[{r, s, ll, atos},
s=1; ll=Mod[l*a, q]; r=1;
While[ll>l && q-ll>l, s++; ll=Mod[ll*a, q]; r=Mod[r*a+1, q]];
If[ll==l, sols[a^s-1, -r b, q], If[q-ll==l, sols[a^s-1, l-r b, q], 1]]]
f[a_, b_, q_]:=Product[f[l, a, b, q], {l, (q-1)/2}]
x[q_]:=Sum[If[GCD[a, q]>1, 0, Sum[f[a, b, q], {b, 0, q-1}]], {a, q-1}]/(q EulerPhi[q])
a[n_]:=x[2n+1]
|
|
PROG
|
(SageMath) # This is a port of the Mathematica program.
def sols(a, b, q):
g = gcd(a, q)
return 0 if mod(b, g) != 0 else g
def F(k, a, b, q):
s, r, m = 1, 1, mod(k*a, q)
while m > k and q - m > k:
s += 1
m = mod(m*a, q)
r = mod(r*a + 1, q)
if m == k: return sols(a^s - 1, -r*b, q)
if m == q-k: return sols(a^s - 1, k - r*b, q)
return 1
def f(a, b, q):
return prod(F(k, a, b, q) for k in (1..(q-1)//2))
def a(n):
q = 2*n + 1
s = sum(0 if gcd(a, q) > 1 else sum(f(a, b, q)
for b in (0..q-1)) for a in (1..q-1))
return s // (q*euler_phi(q))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|