

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 rholabelings, 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) 349355.


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 && qll>l, s++; ll=Mod[ll*a, q]; r=Mod[r*a+1, q]];
If[ll==l, sols[a^s1, r b, q], If[qll==l, sols[a^s1, lr b, q], 1]]]
f[a_, b_, q_]:=Product[f[l, a, b, q], {l, (q1)/2}]
x[q_]:=Sum[If[GCD[a, q]>1, 0, Sum[f[a, b, q], {b, 0, q1}]], {a, q1}]/(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 == qk: 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..(q1)//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..q1)) for a in (1..q1))
return s // (q*euler_phi(q))


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



