Graceful Labeling

Author

Eric W. Weisstein
October 14, 2020

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/GracefulLabeling.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/GracefulLabeling.html.

©2020 Wolfram Research, Inc. except for portions noted otherwise

All graceful graphs

Complete

FindGracefulLabeling[CompleteGraph[2],All]

FindGracefulLabeling[CompleteGraph[3],All]

FindGracefulLabeling[CompleteGraph[4],All]

FindGracefulLabeling[CompleteGraph[6],All]//Timing

FindGracefulLabeling[CompleteGraph[6],All,Method->"CompiledList"]//Timing

FindGracefulLabeling[CompleteGraph[6],All,Method->"CompiledList"]//Timing

And@@(GracefullyLabeledGraphQ[CompleteGraph[4,VertexLabels->Thread[Range[4]->#]]]&/@%106)

Length/@Table[FindGracefulLabeling[GraphData[{"Complete",n}],All],{n,5}]

GraphData["K5","Graceful"]

Counts

SetDirectory[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount"}]]

<<MathWorld`Graphs`

Clear[$GraphDataDirectory]

$GraphDataDirectory

Convert 8-node labeling counts line-by-line to single list

Length[l=ToExpression/@Import["GracefulLabelingCount_08_lines.m","Lines"]]

l[[All,1]]===Range[12346]

Total time:

Total[l[[All,2,1]]]/86400./365. CPUYears

Export["GracefulLabelingCount_08.m",l[[All,2,2]]]

Compare 8-node labeling counts to ungraceful

u1=Flatten[Position[Get["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/GracefulLabelingCount/GracefulLabelingCount_08.m"],0]]

u2=Flatten[Position[ToExpression/@Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/Graceful/GracefulLabeling_08.m","Lines"],{}]]

u1===u2

Convert GracefulLabelingCount + AutomorphismCount -> FundamentalGracefulLabelingCount

Length/@(allcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}])

Length/@(automorphismcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","AutomorphismCount","AutomorphismCount_0"<>ToString[n]<>".m"}]],{n,8}])

Do[Put[((allcounts[[n]])/(2automorphismcounts[[n]]))/.(1/2)->1,FileNameJoin[{$GraphDataDirectory,"Nodes","FundamentalGracefulLabelingCount","FundamentalGracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}]

By nodes

Length/@(counts=Table[Get["GracefulLabelingCount_0"<>ToString[n]<>".m"],{n,8}])

Length/@(fundcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","FundamentalGracefulLabelingCount","FundamentalGracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}])

Ungraceful

(HyperlinkTemplate[A308556, https://oeis.org/A308556None, https://oeis.org/A308556, HyperlinkActionRecycled, HyperlinkActive, , ])

Count[#,0]&/@counts

Graceful

(HyperlinkTemplate[A308548, https://oeis.org/A308548None, https://oeis.org/A308548, HyperlinkActionRecycled, HyperlinkActive, , ])

Count[#,Except[0,_Integer]]&/@counts

Totals of all labelings

(HyperlinkTemplate[A333727, https://oeis.org/A333727None, https://oeis.org/A333727, HyperlinkActionRecycled, HyperlinkActive, , ])

Total[counts,{2}]

Distribution:

Histogram/@counts

Histogram[#,PlotRange->{All,{0,5}}]&/@counts

Histogram[#,"Log"]&/@counts

Totals of all fundamental labelings

XXX

Largest

Largest of fundamental count of all graphs on n nodes:

A339892

Knuth:

1, 1, 1, 5, 26, 126, 680, 3778

Position[fundcounts[[8]],3778]

g1=Graphs[8][[570]]

List@@@EdgeList[g1]

(lab1=FindGracefulLabeling[g1,All])//Timing

Length[fundlab1=GracefulLabelingsReduce[g1,lab1]]

Me:

max=Max/@fundcounts

Table[Max@fundcounts[[n]][[ConnectedGraphIndices[n]]],{n,8}]

Position[fundcounts[[8]],3876]

g2=Graphs[8][[2605]]

List@@@EdgeList[g2]

IsomorphicGraphQ[g2,Graph[Range[8],UndirectedEdge@@@{{1,5},{1,6},{1,7},{2,6},{2,7},{2,8},{3,7},{3,8},{5,8},{6,7},{6,8},{7,8}}]]

(lab2=FindGracefulLabeling[g2,All])//Timing

Length[fundlab2=GracefulLabelingsReduce[g2,lab2]]

And@@(GracefullyLabeledGraphQ[SetProperty[g2,VertexLabels->Thread[Range[8]->#]]]&/@fundlab2)

Largest of all count of all graphs on n nodes:

(HyperlinkTemplate[A333728, https://oeis.org/A333728None, https://oeis.org/A333728, HyperlinkActionRecycled, HyperlinkActive, , ])

max=Max/@counts

Graphs with largest count as a function of node count:

p=Position[#,#2]&@@@Transpose[{counts,max}]

TextGrid[MapIndexed[{#2[[1]],GraphData[{#2[[1]],#},"#"]}&,Flatten[p]],Dividers->All]

Table[GraphData[{"CompleteTripartite",{1,1,n}},"#"],{n,5}]

GraphData[#,"GracefulLabelingCount"]&/@%

(HyperlinkTemplate[A334307, https://oeis.org/A334307None, https://oeis.org/A334307, HyperlinkActionRecycled, HyperlinkActive, , ])

FindSequenceFunction[{112,32,168,1152,9600,97920,1491840,21127680,377395200},n-2]

FindSequenceFunction[{32,168,1152,9600,97920,1491840,21127680,377395200},n-3]

FindGeneratingFunction[{112,32,168,1152,9600,97920,1491840,21127680,377395200},x]

FindGeneratingFunction[{32,168,1152,9600,97920,1491840,21127680,377395200},x]

Graphs up to n=8 with various counts

all=DeleteCases[Flatten[counts],0];

Count[all,_?(Mod[#,2]==1&)]

Count[all,_?(Mod[#,4]==0&)]

Count[all,_?(Mod[#,4]==2&)]

pos=Position[counts,_?(Mod[#,4]==2&)];

TextGrid[Take[SortBy[{#,GraphData[#,"#"],Show[GraphData[#],ImageSize->Tiny],counts[[Sequence@@#]]}&/@pos,Last],10],Dividers->All]

GraphData graphs with various counts

data={#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[countgraphlist={GraphData[#,"FundamentalGracefulLabelings","Count"],#}&/@GraphData["Graceful"],First],First]

Length[countgraphlist]

mod0=Select[countgraphlist,Mod[#[[1]],4]==0&]

Length[mod0]/Length[countgraphlist]//N

mod2=Sort[Select[countgraphlist,Mod[#[[1]],4]==2&]]

Length[mod2]/Length[countgraphlist]//N

Take[Tally[Sort[counts[[All,1]]]],20]

TextGrid[Take[data,20],Dividers->All]

Range[2,48,4]

Fundamental labelings

DeleteCases[{#,GraphData[#,"GracefulLabelingCount"],GraphData[#,"AutomorphismCount"],GraphData[#,"FundamentalGracefulLabelings","Count"],((GraphData[#,"GracefulLabelingCount"])/(2GraphData[#,"AutomorphismCount"]))}&/@GraphData[;;7],{_,_,_,x_Integer,x_}]

Singleton graph

GraphData["SingletonGraph","AutomorphismCount"]

GraphData["SingletonGraph","GracefulLabelings"]

GraphData["SingletonGraph","GracefulLabelingCount"]

GraphData["SingletonGraph","FundamentalGracefulLabelings"]

GraphData["SingletonGraph","FundamentalGracefulLabelings","Count"]

{"Path", 2}

GraphData[{"Path",2},"AutomorphismCount"]

GraphData[{"Path",2},"GracefulLabelings"]

GraphData[{"Path",2},"GracefulLabelingCount"]

GraphData[{"Path",2},"FundamentalGracefulLabelings"]

GraphData[{"Path",2},"FundamentalGracefulLabelings","Count"]

GraphData[{"Path",2},"FundamentalGracefulLabelings"]

Fundamental <-> all labelings

DeleteCases[{#,((GraphData[#,"GracefulLabelingCount"])/(2GraphData[#,"AutomorphismCount"]))}&/@GraphData[{"Graceful","Connected"},;;5],{_,1|1/2}]

FundamentalGracefulLabelings[g_System`Graph,labelings_List]:=Module[{grp=GraphAutomorphismGroup[g],orbits},
orbits=GroupOrbits[grp,labelings,Permute];
(Sort/@Transpose[{orbits,Sort/@(Max[labelings]-orbits)}])[[All,1,1]]//Union
]

AllGracefulLabelings[g_System`Graph,labelings_List]:=Module[{grp=GraphAutomorphismGroup[g],orbits},
Union@@GroupOrbits[grp,Join[fundlab,Max[labelings]-fundlab],Permute]
]

fund=FundamentalGracefulLabelings[GraphData["BullGraph"],GraphData["BullGraph","GracefulLabelings"]]

Length[%]

((GraphData["BullGraph","GracefulLabelingCount"])/(2GraphData["BullGraph","AutomorphismCount"]))

AllGracefulLabelings[GraphData["BullGraph"],fund]===GraphData["BullGraph","GracefulLabelings"]

Pick only symmetrically distinct

Do[Print[{n,Length@RightTransversal[GraphAutomorphismGroup@GraphData[{"CompleteBipartite",{n,n}}],System`SymmetricGroup[2n]]//Timing}],{n,8}]

Table[Binomial[2n-1,n],{n,10}]

PermutationList[#,6]&/@RightTransversal[GraphAutomorphismGroup@GraphData[{"CompleteBipartite",{3,3}}],System`SymmetricGroup[6]]

PermutationList[#,8]&/@RightTransversal[GraphAutomorphismGroup@GraphData[{"CompleteBipartite",{4,4}}],System`SymmetricGroup[8]]

{"CompleteBipartite", {3, 3}}

gn={"CompleteBipartite",{3,3}};

((GraphData[gn,"GracefulLabelingCount"])/(2GraphData[gn,"AutomorphismCount"]))

Length[labelings=GraphData[gn,"GracefulLabelings"]]

grp=GraphAutomorphismGroup[GraphData[gn]]

GroupOrder[grp]

Length[orbits=GroupOrbits[grp,labelings,Permute]]

fundorbit=orbits[[1,1]]

MemberQ[labelings,fundorbit]

fundlab=(Sort/@Transpose[{orbits,Sort/@(Max[labelings]-orbits)}])[[All,1,1]]//Union

GracefullyLabeledGraphQ[SetProperty[GraphData[gn],VertexLabels->Thread[Range[GraphData[gn,"V"]]->#]]]&/@fundlab

Length[full=Union@@GroupOrbits[grp,Join[fundlab,Max[labelings]-fundlab],Permute]]

full==labelings

Parametrized family counts

Code

SimplifyTime[Quantity[MixedMagnitude[l_],MixedUnit[u_]]]:=Module[{drop=FirstPosition[l,_?Positive,{0},{1}][[1]]-1},
Quantity[MixedMagnitude[Drop[l,drop]],MixedUnit[Drop[u,drop]]]]

Table

GraphDataCountTable["GracefulLabelingCount",{"Antiprism"->326576,"Centipede"->334351,"CompleteBipartite"->337793,"Crown"->326747,"Cycle"->333720,"Gear"->337795,{"Grid",2}->337796,"Hypercube"->338005,"Ladder"->333719,"MoebiusLadder"->337794,"Pan"->333729,"Path"->6967,"PathComplement"->336428,"Prism"->336677,"Star"->98558,"Sun"->337792,"Sunlet"->333757,"Wheel"->333672}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"GracefulLabelingCount"],{n,10}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"GracefulLabelingCount"],{n,10}]

Antiprism

Entity["Graph",{"Antiprism",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Antiprism",n},"GracefulLabelingCount"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"GracefulLabelingCount"],{n,6}]

Barbell

seq=Table[GraphData[{"Barbell",n},"GracefulLabelingCount"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"GracefulLabelingCount"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"GracefulLabelingCount"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"GracefulLabelingCount"],{n,20}]

Centipede

(HyperlinkTemplate[A334351, https://oeis.org/A334351None, https://oeis.org/A334351, HyperlinkActionRecycled, HyperlinkActive, , ])

seq=Table[GraphData[{"Centipede",n},"GracefulLabelingCount"],{n,10}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Centipede",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,10}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[Rest@fseq,x]//Head//Timing

CocktailParty

Table[GraphData[{"CocktailParty",n},"Graceful"],{n,20}]

seq=Table[GraphData[{"CocktailParty",n},"GracefulLabelingCount"],{n,20}]

FindSequenceFunction[Rest@DeleteMissing@seq,n-1]//Factor

Complete

Entity["Graph",{"Complete",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Complete",n},"GracefulLabelingCount"],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["GracefulLabelingCount"]

DeleteCases[Block[{m,n},Sort[
{{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"],
XX,
GraphData[#,"GracefulLabelingCount"]
}&/@GraphData["CompleteBipartite"]]],{_,x_,x_}]

CompleteBipartite n×n

(HyperlinkTemplate[A337793, https://oeis.org/A337793None, https://oeis.org/A337793, HyperlinkActionRecycled, HyperlinkActive, , ])

Entity["Graph",{"CompleteBipartite",{n,n}}]["GracefulLabelingCount"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"GracefulLabelingCount"],{n,20}]

Timings from Bert Dobbelaere:

timings={8->4 60+24,9->(189 60+50)}

11390/3600.

Timings on ewwmac:

timings=List@@@{6->.16,7->9.17,8->522.1,9->29718.94}

fit=FindFit[{#,Log10[#2]}&@@@timings,a+b n,{a,b},n]

Table[10^(a+n b/.fit),{n,6,10}]

SimplifyTime/@UnitConvert[Table[Quantity[10^(a+n b/.fit),"Seconds"],{n,6,10}],MixedUnit[{"Days","Hours","Minutes","Seconds"}]]

Quantity[19 24 60,"Minutes"]

Show[{ListLogPlot[timings,PlotStyle->Directive[AbsolutePointSize[10],Red]],LogPlot[10^(a+b n)/.fit,{n,6,10}]},PlotRange->All]

A335619

For n > 1, a(n) is a nonzero multiple of 4*(n!)^2. - Bert Dobbelaere, Sep 30 2020

Table[((GraphData[{"CompleteBipartite",{n,n}},"GracefulLabelingCount"])/(4(((n!))^2))),{n,2,9}]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"CompleteBipartite",{n,n}},{"GracefulLabelingCount","AutomorphismCount"}],{n,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[Rest@fseq,x]//Head//Timing

CompleteTripartite 1×1×n

(HyperlinkTemplate[A339891, https://oeis.org/A339891None, https://oeis.org/A339891, HyperlinkActionRecycled, HyperlinkActive, , ])

seq=Table[GraphData[{"CompleteTripartite",{1,1,n}},"GracefulLabelingCount"],{n,10}]

Table[GraphData[{"CompleteTripartite",{1,1,n}},"Graph","Labeled"],{n,3}]

GraphData[{"CompleteTripartite",{1,1,1}},"GracefulLabelings"]

GraphData[{"CompleteTripartite",{1,1,2}},"GracefulLabelings"]

GraphData[{"CompleteTripartite",{1,1,3}},"GracefulLabelings"]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

seq2=Table[GraphData[{"CompleteTripartite",{1,1,n}},"GracefulLabelingCount"],{n,10}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq2,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq2,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing@seq2,x]//Head//Timing

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"CompleteTripartite",{1,1,n}},{"GracefulLabelingCount","AutomorphismCount"}],{n,10}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[fseq,x]//Head//Timing

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["GracefulLabelingCount"]

Table[{k,m,n},{k,5},{m,k},{n,m}]

Table[GraphData[{"CompleteTripartite",{k,m,n}},"GracefulLabelingCount"],{k,5},{m,k,5},{n,m,5}]//Column//TraditionalForm

Block[{k,m,n},Sort[{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],GraphData[#,"GracefulLabelingCount"],XXX}&/@GraphData["CompleteTripartite"]]]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["GracefulLabelingCount"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"GracefulLabelingCount"],{n,10}]

FindSequenceFunction[Rest@DeleteMissing@seq,n-1]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"GracefulLabelingCount"],{n,2,10}]

Crown

seq=Table[GraphData[{"Crown",n},"GracefulLabelingCount"],{n,3,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"GracefulLabelingCount"],{n,3,8}]

Cycle

(HyperlinkTemplate[A333720, https://oeis.org/A333720None, https://oeis.org/A333720, HyperlinkActionRecycled, HyperlinkActive, , ])

Entity["Graph",{"Cycle",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Cycle",n},"Graceful"],{n,3,20}]

seq=Table[GraphData[{"Cycle",n},"GracefulLabelingCount"],{n,3,20}]

FindGeneratingFunction[DeleteMissing@seq,x]//Timing

seq=ToExpression[StringSplit/@Rest[Import["https://oeis.org/A333720/b333720.txt","Lines"]]][[All,2]]

seq1=seq[[1;;All;;4]]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq1,k]]//Head//Timing}],{k,0,3}]

seq2=seq[[2;;All;;4]]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq2,k]]//Head//Timing}],{k,0,3}]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Cycle",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,3,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[fseq,x]//Head//Timing

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"GracefulLabelingCount"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"GracefulLabelingCount"],{n,3,14}]

MaxMemoryUsed[lab=FindGracefulLabeling[GraphData@{"Dipyramid",6},All]]//Timing

lab

Empty

Entity["Graph",{"Empty",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Empty",n},"GracefulLabelingCount"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"GracefulLabelingCount"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"GracefulLabelingCount"],{n,10}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"GracefulLabelingCount"],{n,2,10}]

Gear

A337795

seq=Table[GraphData[{"Gear",n},"GracefulLabelingCount"],{n,3,20}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing[seq],x]//Head//Timing

Table[((GraphData[{"Gear",n},"GracefulLabelingCount"])/(2GraphData[{"Gear",n},"AutomorphismCount"])),{n,3,7}]

Timings on ewwmac:

timings=List@@@{5->1.57,6->95.87,7->6792.00}

fit=FindFit[{#,Log10[#2]}&@@@timings,a+b n,{a,b},n]

Table[10^(a+n b/.fit),{n,5,9}]

SimplifyTime/@UnitConvert[Table[Quantity[10^(a+n b/.fit),"Seconds"],{n,5,9}],MixedUnit[{"Days","Hours","Minutes","Seconds"}]]

UnitConvert[Quantity[15800.,"Minutes"],"Days"]

Show[{ListLogPlot[timings,PlotStyle->Directive[AbsolutePointSize[8],Red]],LogPlot[10^(a+b n)/.fit,{n,5,9}]},PlotRange->All]

Gear(8) to 1011364.09 s = 11.7 days on byblis67

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Gear",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,3,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindLinearRecurrence[Drop[fseq,3]]

FindGeneratingFunction[fseq,x]//Head//Timing

GeneralizedPetersen

Sort[{"GeneralizedPetersen"/.GraphData[#,"NotationRules"],GraphData[#,"GracefulLabelingCount"]}&/@GraphData["GeneralizedPetersen"]]

Grid 3×n

seq=Table[GraphData[{"Grid",Sort[{3,n}]},"GracefulLabelingCount"],{n,10}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["GracefulLabelingCount"]

DeleteCases[Block[{m,n},Sort[{
{m,n}="Grid"/.GraphData[#,"NotationRules"],
GraphData[#,"GracefulLabelingCount"],
Min[m,n]}&/@Select[GraphData["Grid"],Length["Grid"/.GraphData[#,"NotationRules"]]==2&]]],{_,x_,x_}]

Grid n×n

A337796

Entity["Graph",{"Grid",{n,n}}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Grid",{n,n}},"GracefulLabelingCount"],{n,10}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing[seq],x]//Head//Timing

Timings on ewwmac:

timings=List@@@{3->0.02,4->125494.62}

fit=FindFit[{#,Log10[#2]}&@@@timings,a+b n,{a,b},n]

Table[10^(a+n b/.fit),{n,3,5}]

SimplifyTime/@UnitConvert[Table[Quantity[10^(a+n b/.fit),"Seconds"],{n,3,5}],MixedUnit[{"Years","Days","Hours","Minutes","Seconds"}]]

Show[{ListLogPlot[timings,PlotStyle->Red],LogPlot[10^(a+b n)/.fit,{n,3,5}]},PlotRange->All]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Grid",{n,n}},{"GracefulLabelingCount","AutomorphismCount"}],{n,10}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[Rest@fseq,x]//Head//Timing

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["GracefulLabelingCount"]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Grid",{n,n,n}},"GracefulLabelingCount"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"GracefulLabelingCount"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"GracefulLabelingCount"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"GracefulLabelingCount"],{n,3,20}]

FindSequenceFunction[DeleteMissing@seq,n-2]

Hypercube

A338005

Entity["Graph",{"Hypercube",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Hypercube",n},"GracefulLabelingCount"],{n,0,10}]

Bert Dobbelaere 2020-02-06:
I also counted  466308864 graceful labelings for the 4 dimensional hypercube graph (16V/32E).
For 5 dimensions (32V/80E) it took a long time to just produce one  solution (although there are probably many more). I have no ambition to enumerate them.

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Hypercube",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,10}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[fseq,x]//Head//Timing

Keller

Entity["Graph",{"Keller",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Keller",n},"GracefulLabelingCount"],{n,5}]

King m×n

Table[GraphData[{"King",{m,n}},"GracefulLabelingCount"],{n,10},{m,n}]//Column//TraditionalForm

King 2×n

seq=Table[GraphData[{"King",Sort[{2,n}]},"GracefulLabelingCount"],{n,10}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"GracefulLabelingCount"],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["GracefulLabelingCount"]

Table[GraphData[{"Knight",{m,n}},"GracefulLabelingCount"],{n,10},{m,n}]//Column

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Knight",{n,n}},"GracefulLabelingCount"],{n,20}]

Ladder

(HyperlinkTemplate[A333719, https://oeis.org/A333719None, https://oeis.org/A333719, HyperlinkActionRecycled, HyperlinkActive, , ])

Entity["Graph",{"Ladder",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Ladder",n},"GracefulLabelingCount"],{n,20}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing@seq,x]//Timing

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Ladder",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

FindLinearRecurrence[Drop[fseq,3]]

FindGeneratingFunction[Rest@fseq,x]//Head//Timing

LadderRung

seq=Table[GraphData[{"LadderRung",n},"GracefulLabelingCount"],{n,20}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"GracefulLabelingCount"],{n,3}]

MoebiusLadder

A337794

Entity["Graph",{"MoebiusLadder",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"MoebiusLadder",n},"GracefulLabelingCount"],{n,3,25}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing[seq],x]//Head//Timing

Table[((GraphData[{"MoebiusLadder",n},"GracefulLabelingCount"])/(2GraphData[{"MoebiusLadder",n},"AutomorphismCount"])),{n,3,9}]

Timings on ewwmac:

timings=List@@@{6->1,7->67.95,8->5087.68}

fit=FindFit[{#,Log10[#2]}&@@@timings,a+b n,{a,b},n]

Table[10^(a+n b/.fit),{n,6,10}]

SimplifyTime/@UnitConvert[Table[Quantity[10^(a+n b/.fit),"Seconds"],{n,6,10}],MixedUnit[{"Days","Hours","Minutes","Seconds"}]]

UnitConvert[Quantity[15800.,"Minutes"],"Days"]

Show[{ListLogPlot[timings,PlotStyle->Directive[AbsolutePointSize[6],Red]],LogPlot[10^(a+b n)/.fit,{n,6,10}]},PlotRange->All]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"MoebiusLadder",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,3,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[fseq,x]//Head//Timing

Mycielski

Entity["Graph",{"Mycielski",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Mycielski",n},"GracefulLabelingCount"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Odd",n},"GracefulLabelingCount"],{n,7}]

Pan

(HyperlinkTemplate[A333729, https://oeis.org/A333729None, https://oeis.org/A333729, HyperlinkActionRecycled, HyperlinkActive, , ])

seq=Table[GraphData[{"Pan",n},"GracefulLabelingCount"],{n,3,20}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[DeleteMissing[seq],x]//Head//Timing

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Pan",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,3,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[fseq,x]//Head//Timing

Path

Entity["Graph",{"Path",n}]["GracefulLabelingCount"]

Replace[Table[GraphData[{"Path",n},"GracefulLabelings"],{n,20}],l_List:>Missing[All,l[[1]]],{1}]//Column

seq=Table[GraphData[{"Path",n},"GracefulLabelingCount"],{n,20}]

All labelings (number of graceful permutations): (HyperlinkTemplate[A006967, https://oeis.org/A006967None, https://oeis.org/A006967, HyperlinkActionRecycled, HyperlinkActive, , ])

https://oeis.org/A006967/b006967.txt

seq0=DeleteCases[Import["https://oeis.org/A006967/b006967.txt","Table"],{}][[2;;,2]]

Length[seq0]

Fundamentally different labelings:

Entity["Graph",{"Path",n}]["AutomorphismCount"]

seq=Ceiling[seq0/4]

Do[Print[{k,FindSequenceFunction[Drop[seq,k],n]//Head//Timing}],{k,6}]

Do[Print[{k,FindLinearRecurrence[Drop[seq,k]]//Head//Timing}],{k,6}]

FindGeneratingFunction[seq,x]//Head//Timing

PathComplement

(HyperlinkTemplate[A336428, https://oeis.org/A336428None, https://oeis.org/A336428, HyperlinkActionRecycled, HyperlinkActive, , ])

seq=Table[GraphData[{"PathComplement",n},"GracefulLabelingCount"],{n,20}]

FindGeneratingFunction[Take[seq,8],x]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"PathComplement",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,10}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k+1]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[Rest@fseq,x]//Head//Timing

Prism

(HyperlinkTemplate[A336677, https://oeis.org/A336677None, https://oeis.org/A336677, HyperlinkActionRecycled, HyperlinkActive, , ])

Entity["Graph",{"Prism",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Prism",n},"GracefulLabelingCount"],{n,3,25}]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Prism",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,3,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[fseq,x]//Head//Timing

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"GracefulLabelingCount"],{n,10}]

Rook m×n

Table[GraphData[{"Rook",{m,n}},"GracefulLabelingCount"],{n,10},{m,n}]//Column

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"GracefulLabelingCount"],{n,10}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"GracefulLabelingCount"],{n,10}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"GracefulLabelingCount"],{n,4}]

SierpinskiSieve

seq=Table[GraphData[{"SierpinskiSieve",n},"GracefulLabelingCount"],{n,5}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"GracefulLabelingCount"],{n,6}]

StackedBook m×n

Table[GraphData[{"StackedBook",{m,n}},"GracefulLabelingCount"],{m,10},{n,10}]//Column//TraditionalForm

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"GracefulLabelingCount"],{n,10}]

Star

A000012

Entity["Graph",{"Star",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Star",n},"GracefulLabelingCount"],{n,25}]

Sun

(HyperlinkTemplate[A337792, https://oeis.org/A337792None, https://oeis.org/A337792, HyperlinkActionRecycled, HyperlinkActive, , ])

seq=Table[GraphData[{"Sun",n},"GracefulLabelingCount"],{n,3,20}]

Sunlet

(HyperlinkTemplate[A333757, https://oeis.org/A333757None, https://oeis.org/A333757, HyperlinkActionRecycled, HyperlinkActive, , ])

seq=Table[GraphData[{"Sunlet",n},"GracefulLabelingCount"],{n,3,20}]

Head/@Table[FindSequenceFunction[Drop[DeleteMissing@seq,k],n-2-k],{k,0,2}]

Table[FindLinearRecurrence[Drop[DeleteMissing@seq,k]],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Sunlet",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,3,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindLinearRecurrence[Drop[fseq,2]]

FindGeneratingFunction[fseq,x]//Head//Timing

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"GracefulLabelingCount"],{n,6,10}]

Transposition

Entity["Graph",{"Transposition",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Transposition",n},"GracefulLabelingCount"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"GracefulLabelingCount"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"GracefulLabelingCount"],{n,0,10}]

TriangularHoneycombAcuteKnight

Table[GraphData[{"TriangularHoneycombAcuteKnight",n}],{n,7}]

Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"ConnectedComponents","Name"],{n,8}]//Column

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"GracefulLabelingCount"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"GracefulLabelingCount"],{n,9}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"GracefulLabelingCount"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"GracefulLabelingCount"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"GracefulLabelingCount"],{n,10}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"GracefulLabelingCount"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"GracefulLabelingCount"],{n,3,20}]

Wheel

(HyperlinkTemplate[A333672, https://oeis.org/A333672None, https://oeis.org/A333672, HyperlinkActionRecycled, HyperlinkActive, , ])

Entity["Graph",{"Wheel",n}]["GracefulLabelingCount"]

seq=Table[GraphData[{"Wheel",n},"GracefulLabelingCount"],{n,4,20}]

Do[Print[{k,FindSequenceFunction[Drop[DeleteMissing@seq,k],n-3-k]//Head//Timing}],{k,0,2}]

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@seq,k]]//Head//Timing}],{k,0,2}]

FindGeneratingFunction[DeleteMissing@seq,x]

Fundamental labelings

fseq=#1/(2#2)&@@@DeleteCases[Table[GraphData[{"Wheel",n},{"GracefulLabelingCount","AutomorphismCount"}],{n,4,20}],{_Missing,_}]

Do[Print[{k,FindSequenceFunction[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

Do[Print[{k,FindLinearRecurrence[Drop[fseq,k]]//Head//Timing}],{k,0,3}]

FindGeneratingFunction[fseq,x]//Head//Timing

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"GracefulLabelingCount"],{n,2,10}]

Algorithm

Select only those with 0 and m

ReducedPermutationsPick[m_,n_]:=Select[Permutations[Range[0,m],{n}],ContainsAll[{0,m}]]

red1=ReducedPermutationsPick[6,4]

p2=With[{m=6,n=4},Pick[p=Permutations[Range[0,m],{n}],ContainsAll[{0,m}]/@p]]

Developer`PackedArrayQ[p2]

Length/@{Permutations[Range[6],{4}],p1}

lab=GraphData["K4","GracefulLabelings"]

Complement[lab,s1]

With[{m=6,n=4},Pick[p=Permutations[Range[0,m],{n}],ContainsAll[{0,m}]/@p]]//Developer`PackedArrayQ

With[{m=6,n=4},Pick[p=Permutations[Range[0,m],{n}],Boole[ContainsAll[{0,m}]/@p],1]]//Developer`PackedArrayQ

Developer`PackedArrayQ[p]

MaxMemoryUsed[perm1=Permutations[Range[0,20],{6}]]//Timing

Developer`PackedArrayQ[perm1]

From Michael

2020-04-02

reducedPermutations[n_,k_,must_]:=Module[{rest=Complement[Range[n],must],tuples},
tuples=Join[must,#]&/@Subsets[rest,{k-2}];
Sort[Flatten[Permutations/@tuples,1]]]

MaxMemoryUsed[perm2=reducedPermutations[20,6,{0,20}]]//Timing

perm2===perm1

red2=reducedPermutations[6,4,{0,6}]

red1==red2

<<MathWorld`Graphs`

Select[GraphData[4],GraphData[#,"M"]===6&]

SameQ@@(FindGracefulLabeling[GraphData[{"Ladder",4}],All,Debug->True,"PermutationMethod"->#]&/@{None,Flatten,Join})

Print[{#,MaxMemoryUsed[FindGracefulLabeling[GraphData[{"Ladder",4}],All,"PermutationMethod"->#]]//Timing}]&/@{None,Flatten,Join};

Print[{#,MaxMemoryUsed[FindGracefulLabeling[GraphData[{8,375}],All,"PermutationMethod"->#]]//Timing}]&/@{None,Flatten,Join};

Print[{#,MaxMemoryUsed[FindGracefulLabeling[GraphData[{7,670}],All,"PermutationMethod"->#]]//Timing}]&/@{None,Flatten,Join};

Print[{#,MaxMemoryUsed[FindGracefulLabeling[GraphData[{"Heptahedral",18}],All,"PermutationMethod"->#]]//Timing}]&/@{None,Flatten,Join};

Print[{#,MaxMemoryUsed[FindGracefulLabeling[GraphData[{7,767}],All,"PermutationMethod"->#]]//Timing}]&/@{None,Flatten,Join};

Built-in subsets

MaxMemoryUsed[data={#,GraphData[#,"GracefulLabelingCount"],Length@FindGracefulLabeling[GraphData[#],All]}&/@GraphData["Graceful",;;6]]//AbsoluteTiming

DeleteCases[data,{_,x_,x_}]

Compiled do (packed) subsets

MaxMemoryUsed[data={#,GraphData[#,"GracefulLabelingCount"],Length@FindGracefulLabeling[GraphData[#],All]}&/@GraphData["Graceful",;;6]]//AbsoluteTiming

DeleteCases[data,{_,x_,x_}]

Constraints

Vertex labels must contain both 0 and m

Table[Cases[{#,Abs[Subtract@@#]}&/@Subsets[Range[0,k],{2}],{_,k}],{k,10}]

data=DeleteCases[GraphData[#,{"#","M","GracefulLabelings"}]&/@GraphData["Graceful"],{_,_,Missing[_]}]/.Missing[_,l_List]:>{l}

Cases[{#,And@@(ContainsAll[{0,#2}]/@#3)}&@@@data,{g_,False}:>g]

Subtractive complements must be present