Maximally Graceful Tree

Author

Eric W. Weisstein
December 30, 2024

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

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

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

Sources

Knuth (2024)

Anick (2016)

Anick (2016)

Figure

A379102

Table[Max[DeleteMissing[GraphData[#,"GracefulLabelingCount"]&/@GraphData["Tree",n]]],{n,17}]

Anick divided by 2:

{36,104,228,734,3554,10498,42214,169492,865538,20798700}/2

TextGrid[data=MapIndexed[Prepend[#,#2[[1]]]&,{#[[1,1]],Rest/@#}&/@Table[SplitBy[SortBy[
DeleteCases[
GraphData[#,{"GracefulLabelingCount","#","Graph"}]&/@GraphData["Tree",n],
{_Missing,__}
],
First],First][[-1]],{n,17}]]/.g_Graph:>Annotate[g,ImageSize->Tiny],Dividers->All]

expanded=Flatten[Table[{data[[i,1]],data[[i,2]],#[[2]]}&/@data[[i,3]],{i,Length[data]}],1]

GraphicsGrid[Partition[Annotate[StyleGraphs@#3,PlotLabel->Column[{Row[{Style["n",Italic],"==",#}," "],Row[{#2,If[#2==1,"labeling","labelings"]}," "]},Alignment->Center,BaseStyle->Directive[Black,FontFamily->"Times"]]]&@@@expanded,UpTo[6]],Dividers->All,Alignment->Top,ImageSize->700]

Constuction

7 nodes / 6 edges

RecognizeGraph[Graph6A=EdgeAdd[PathGraph[Range@6,VertexLabels->Automatic],4\[UndirectedEdge]7]]

13 nodes / 12 edges

Anick (2016)

v=Join[Table[{i,0},{i,0,7}],{{2,1},{4,1},{5/2,-1},{7/2,-1},{9/2,-1}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,3,4,5,6,7,8],{3,9},{5,10},{4,11},e[4,12,13]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

IndexGraph@Graph[EdgeList[g]]

14 nodes / 13 edges

Anick (2016)

v=Join[Table[{i,0},{i,0,7}],{{2,1},{4,1},{5/2,-1},{7/2,-1},{9/2,-1},{11/2,-1}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,3,4,5,6,7,8],{3,9},{5,10},e[11,4,12],{6,14},{12,13}},VertexCoordinates->v,VertexLabels->Automatic]

IndexGraph@Graph[EdgeList[g]]

15 nodes / 14 edges

Anick (2016)

v=Join[Table[{i,0},{i,0,7}],{{2,1},{3,1},{5/2,-1},{3/2,-1},{1/2,-1},{7/2,-1},{9/2,-1}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[{1,8}],{3,9},e[13,12,11,4,14,15],{4,10}},VertexCoordinates->v,VertexLabels->Automatic]

IndexGraph@Graph[EdgeList[g]]

16 nodes / 15 edges

Anick (2016)

v=Join[Table[{i,0},{i,0,7}],{{2,1},{3,1},{5/2,-1},{3/2,-1},{1/2,-1},{7/2,-1},{9/2,-1},{4,1}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[{1,8}],{3,9},e[13,12,11,4,14,15],{4,10},{5,16}},VertexCoordinates->v,VertexLabels->Automatic]

IndexGraph@Graph[EdgeList[g]]

17 nodes / 16 edges

Anick (2016)

Knuth (2024, Fig. 42)

<<MathWorld`Graphs`

v={{549,77},{496,121},{514,16},{450,66},{384,102},{320,137},{253,137},{166,103},{80,136},{99,66},{34,102},{405,59},{341,24},{275,67},{212,15},{145,50},{80,15}};
g=ScaleGraph@Graph[Range@Length@v,UndirectedEdge@@@{e[11,10,8,9],e[17,16,15,14],e[8,14,7],e[6,5,4,3],e[4,2,1],e[5,14,13,12]},VertexCoordinates->v,VertexLabels->Automatic]

Through[{VertexCount,EdgeCount}[g]]

RecognizeGraph[g]

IndexGraph@Graph[EdgeList[g]]

Special tree

GraphData["Tree",17]

Knuth 2024

Knuth (2024, Fig. 41)

v={#,#2-1}&@@@Join[Subdivide[{0,0},{2,1},2],Rest@Subdivide[{2,1},{0,2},2],Sequence@@Table[{i,j},{i,3,6},{j,{0,2}}],{{3,1},{8,0},{8,2},{8,1}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,3,4,5],e[7,14,6],e[9,14,8],e[11,14,10],e[13,14,12],e[16,14,15],{14,17},{3,14}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphData

AddIndexedClass

rules=Flatten[MapIndexed[Rule[#,#2]&,data[[All,3,All,1]],{2}],1]

AddIndexedClass["MaximallyGracefulTree",rules,14.3,"AddClass"->False]

RenameGraphFiles[]

GraphDataString

MaximallyGracefulTree's

countrules=Rule@@@MapIndexed[{#2[[1]],#}&,{1,1,1,1,3,6,18,52,114,367,1777,5249,21107,84746,432769,10399350}]

trees={
{"MaximallyGracefulTree",{13,1}}->,
{"MaximallyGracefulTree",{14,1}}->,
{"MaximallyGracefulTree",{15,1}}->,
{"MaximallyGracefulTree",{16,1}}->,
{"MaximallyGracefulTree",{17,1}}->
};

file=OpenWrite["~/maximall-graceful-trees.m"]

WriteString[file,GraphDataString[#2,
"StandardName"->#,
"Name"->ToString[#1[[2,1]]]<>"maximally graceful tree 1",
"Classes"->{"Graceful"},
"GracefulLabelingCount"->Lookup[countrules,#[[2,1]]],
"Information"->"MaximallyGracefulTree",
"NotationRules"->{#},
"Skip"->{"Minors"}
]]&@@@trees;

Close[file]

SmallGracefulLabelingCountTree

file=OpenWrite["~/small-graceful-labling-tree.m"]

WriteString[file,GraphDataString[,
"StandardName"->"SmallGracefulLabelingCountTree",
"Name"->"small graceful labeling tree",
"Classes"->{"Graceful"},
"Information"->"GracefulLabeling",
"Skip"->{"Minors"}
]];

Close[file]