Maximally Graceful Graph

Author

Eric W. Weisstein
January 7, 2025

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

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

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

Source

Knuth, D.E.  Problem 97 in The Art of Computer Programing, Vol. 4, Pre-Fascicle 7A, §7.2.2.3, pp. 121 and , 2024.

A002494: simple graphs with no isolated vertices

1, 2, 7, 23, 122, 888, 11302

A379575: Total numbers of fundamentally distinct graceful labelings among all simple graphs on n vertices having no isolated points.

1, 2, 13, 157, 3292

Figures

All graphs

TextGrid[data=MapIndexed[Prepend[#,#2[[1]]]&,{#[[1,1]],Rest/@#}&/@Table[SplitBy[SortBy[
DeleteCases[
GraphData[#,{"GracefulLabelingCount","#","Graph"}]&/@GraphData[n],
{_Missing,__}
],
First],First][[-1]],{n,8}]]/.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]

Length[expanded]

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[5]],Dividers->All,Alignment->Top,ImageSize->700]

Connected

TextGrid[data=MapIndexed[Prepend[#,#2[[1]]]&,{#[[1,1]],Rest/@#}&/@Table[SplitBy[SortBy[
DeleteCases[
GraphData[#,{"GracefulLabelingCount","#","Graph"}]&/@GraphData["Connected",n],
{_Missing,__}
],
First],First][[-1]],{n,8}]]/.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]

Length[expanded]

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[5]],Dividers->All,Alignment->Top,ImageSize->700]

StyleGraphs[GraphData[{"MaximumPlanarEmbedding",{8,1}}],ImageSize->Small,PlotLabel->"3778 labelings",LabelStyle->Directive[14,Black,FontFamily->"Times"]]

GraphData[{"MaximumPlanarEmbedding",{8,1}},"GracefulLabelingCount"]

GraphData[{"MaximumPlanarEmbedding",{8,1}},"StandardNames"]

GraphData[{"MaximumPlanarEmbedding",{8,1}},"PlanarEmbeddingCount"]

Counts

fundcounts=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]],{n,8}];

Length[fundcounts9=ToExpression[StringSplit[StringDrop[#,-2],","][[-1]]]&/@Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Nodes/GracefulLabelingCount/GracefulLabelingCount_09_lines.m","Lines"]]

Maximally graceful (not necessarily connected)

A379395

GraphData:

TextGrid[Table[MaximalBy[DeleteCases[GraphData[#,{"V","GracefulLabelingCount","#","Graph"}]&/@GraphData["Graceful",n],{_,_Missing,_,_}]/.g_Graph:>Annotate[g,ImageSize->Tiny],#[[2]]&][[1]],{n,4,21}],Dividers->All]

GraphIndex@GraphData[{"MaximumPlanarEmbedding",{9,4}}]

maxplan=Select[GraphData[All],MatchQ[GraphData[#,"StandardNames"],{___,{"MaximumPlanarEmbedding",{9,_},___}}]&]

Annotate[GraphData[#],PlotLabel->GraphData[#,"GracefulLabelingCount"]]&/@maxplan

Computed over all graphs:

Max/@fundcounts

Max[fundcounts9]

PositionLargest[fundcounts9]

g9max=Graphs[9][[1056]]

RecognizeGraph@g9max

RecognizeGraph/@ConnectedGraphComponents[g9max]

SymmetricallyDistinctLabelings[g9max,FindGracefulLabeling[g9max, All], "AdditivelyConjugateEquivalent" -> True]//Length//Timing

data=Table[
{
n,
pos=Flatten[Position[fundcounts[[n]],Max[fundcounts[[n]]]]],
gs=Graphs[n][[pos]],
RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs
},{n,8}]

Maximally graceful connected [same as "with no isolated points" up to at least 8 vertices]

A339892 (no isolated points)

GraphData:

TextGrid[Table[MaximalBy[DeleteCases[GraphData[#,{"V","GracefulLabelingCount","#","Graph"}]&/@GraphData[{"Connected","Graceful"},n],{_,_Missing,_,_}]/.g_Graph:>Annotate[g,ImageSize->Tiny],#[[2]]&][[1]],{n,4,21}],Dividers->All]

Table[Max[GraphData[#,"GracefulLabelingCount"]&/@GraphData[{"Connected","Graceful"},n]],{n,25}]/.Max[i_,_Missing]:>i

GraphIndex@GraphData[{"MaximumPlanarEmbedding",{9,4}}]

Computed over all graphs:

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

Max[fundcounts9[[Select[ConnectedGraphIndices[9],#≤Length[fundcounts9]&]]]]

data2=Table[
{
n,
pos=Flatten[Position[cnts=fundcounts[[n]][[ConnectedGraphIndices[n]]],Max[cnts]]],
gs=Graphs[n][[ConnectedGraphIndices[n]]][[pos]],
RecognizeGraph[#,"Cache"->"InternalOnly"]&/@gs
},{n,8}]

data[[All,-1]]

GetGraphData[{"MaximumPlanarEmbedding",{8,1}},"File"]

Maximally graceful not allowing isolated vertices

A339892

GraphData:

Table[Max[GraphData[#,"GracefulLabelingCount"]&/@Select[GraphData["Graceful",n],GraphData[#,"MinimumVertexDegree"]>0&]],{n,9}]

TextGrid[Table[MaximalBy[DeleteCases[GraphData[#,{"V","GracefulLabelingCount","#","Graph"}]&/@Select[GraphData["Graceful",n],GraphData[#,"MinimumVertexDegree"]>0&],{_,_Missing,_,_}]/.g_Graph:>Annotate[g,ImageSize->Tiny],#[[2]]&][[1]],{n,4,21}],Dividers->All]

Computed over all graphs:

mindegrees=Table[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","MinimumVertexDegree","MinimumVertexDegree_0"<>ToString[n]<>".m"}]],{n,9}];

NoIsolatedPointPositions=Table[Flatten@Position[mindegrees[[n]],_Integer?Positive],{n,9}];

Table[Max[fundcounts[[n]][[NoIsolatedPointPositions[[n]]]]],{n,8}]

Max[fundcounts9[[Select[NoIsolatedPointPositions[[9]],#≤Length[fundcounts9]&]]]]

Position[fundcounts9,%]

g9max=Graphs[9][[1060]]

RecognizeGraph@g9max

SymmetricallyDistinctLabelings[g9max,FindGracefulLabeling[g9max, All], "AdditivelyConjugateEquivalent" -> True]//Length//Timing

data=Table[
MaximalBy[
DeleteCases[
MapIndexed[{#,#2[[1]],Min[VertexDegree[Graphs[n][[#2[[1]]]]]]>0}&,Import[FileNameJoin[{$GraphDataDirectory,"Nodes","GracefulLabelingCount","GracefulLabelingCount_0"<>ToString[n]<>".m"}]]],
{_,_,False}
],
First
],{n,8}]

data[[2;;,1,1]]

Embeddings

<<MathWorld`Graphs`

{"MaximallyGraceful", {6, 1}}

Names

GraphData[{"MaximallyGraceful",{6,1}},"StandardName"]

GraphData[{"MaximallyGraceful",{6,1}},"StandardNames"]

Primary

GraphData[{"MaximallyGraceful",{6,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyGraceful",{6,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyGraceful",{6,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"MaximallyGraceful",{6,1}}]]

Default embedding

GraphPlot[RotateGraph[Graph[GraphData[{"MaximallyGraceful",{6,1}},"VertexList"],GraphData[{"MaximallyGraceful",{6,1}},"Edges"]],-Pi/4-.2]]

s=Sqrt[3]/2;
v={{0,0},{1,0},{1,1},{0,1},{-s,1/2},{-s,3/2}};
Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=RotateGraph[FindCorrespondingGraph[, v],-Pi/2]

s=Sqrt[3]/2;
v={{0,0},{1,0},{1,1},{0,1},{1/2,1+s},{2,1}};
Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,3,5,4,1,3,6],e[3,4,2]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

s=Sqrt[3]/2;
v={{0,0},{1,0},{1/2,s},{3/2,s},{2,0}};
AppendTo[v,Mean[v[[{1,2,3}]]]];
Graph[Range@Length@v,UndirectedEdge@@@{e[5,2,1,3,2,4,3,6,1],{2,6}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs=UnlabelGraph/@{,}

Degenerate

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyGraceful",{6,1}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"MaximallyGraceful",{6,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyGraceful",{6,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"MaximallyGraceful",{6,1}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyGraceful",{6,1}},"Hamiltonian"]

GraphData[{"MaximallyGraceful",{6,1}},"LCF"]

GraphData[{"MaximallyGraceful",{6,1}},"HamiltonianCycleCount"]

Planar

GraphData[{"MaximallyGraceful",{6,1}},"Planar"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyGraceful",{6,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyGraceful",{6,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyGraceful",{6,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyGraceful",{6,1}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"MaximallyGraceful",{6,1}},{"RCN","CN"}]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"MaximallyGraceful",{6,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyGraceful",{6,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"MaximallyGraceful",{6,1}},"Circulant"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyGraceful",{6,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyGraceful",{6,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyGraceful",{6,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyGraceful",{6,1}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"MaximallyGraceful",{6,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyGraceful",{6,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyGraceful",{6,1}}&]

RootGraph[GraphData[{"MaximallyGraceful",{6,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyGraceful",{6,1}},"Halin"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyGraceful",{6,1}},"Rigid"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyGraceful",{6,1}},"Flexible"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyGraceful",{6,1}},"LCF"]

GraphData[{"MaximallyGraceful",{6,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyGraceful",{6,1}},"LCFSignature"]

GraphData[{"MaximallyGraceful",{6,1}},"LCFNotations"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"MaximallyGraceful",{6,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyGraceful",{6,1}}],Debug->True]//Timing

GraphData[{"MaximallyGraceful",{6,1}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyGraceful",{6,1}},"VertexList"],GraphData[{"MaximallyGraceful",{6,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyGraceful",{6,1}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyGraceful",{6,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyGraceful",{6,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"MaximallyGraceful",{6,1}},"Matchstick"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyGraceful",{6,1}},"Edges"]]

3D construction

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

3D All

GraphData[{"MaximallyGraceful",{6,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyGraceful",{6,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyGraceful",{6,1}},"Polyhedral"]

GraphData[{"MaximallyGraceful",{6,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyGraceful", {7, 1}}

Names

GraphData[{"MaximallyGraceful",{7,1}},"StandardName"]

GraphData[{"MaximallyGraceful",{7,1}},"StandardNames"]

Primary

GraphData[{"MaximallyGraceful",{7,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyGraceful",{7,1}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"MaximallyGraceful",{7,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"MaximallyGraceful",{7,1}}]]

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{"MaximallyGraceful",{7,1}},"VertexList"],GraphData[{"MaximallyGraceful",{7,1}},"Edges"],GraphLayout->"SpringEmbedding"],{5,1}]

s=Sqrt[3]/2;
v={{0,0},{1,0},{1,1},{0,1},{2,1},{1/2,1+s},{-s,1/2}};
Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

s=Sqrt[3]/2;
v={{0,0},{1,0},{1,1},{0,1},{1+s,1/2},{1/2,1+s},{-s,1/2}};
Graph[Range@Length@v,UndirectedEdge@@@{e[5,3,4,7,1,2,3,6,4,1,3],{2,4}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphPlot@RotateGraph[GraphicsToGraph@,{3,2}]

s=Sqrt[3]/2;
v={{0,0},{1,0},{2,0},{1/2,s},{3/2,s},{5/2,s}};
AppendTo[v,Mean[v[[{2,4,5}]]]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[6,5,4,1,2,3,5,2,4,7,5],{2,7}},VertexCoordinates->v,VertexLabels->Automatic]

s=Sqrt[3]/2;
v={{0,0},{1,0},{2,0},{1/2,s},{3/2,s},{1,2s}};
AppendTo[v,Mean[v[[{2,4,5}]]]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[6,5,4,1,2,3,5,2,4,7,5],{2,7}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

v={{0,0},{1,0},{1,1},{1/2,1},{0,1},{2,0}};
AppendTo[v,Mean[v[[{1,2,4}]]]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[6,2,1,5,4,3,2,7,1,4,2],{4,7}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs=UnlabelGraph/@{,,,}

gs={,}

Degenerate

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyGraceful",{7,1}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"MaximallyGraceful",{7,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyGraceful",{7,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"MaximallyGraceful",{7,1}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyGraceful",{7,1}},"Hamiltonian"]

GraphData[{"MaximallyGraceful",{7,1}},"LCF"]

GraphData[{"MaximallyGraceful",{7,1}},"HamiltonianCycleCount"]

Planar

GraphData[{"MaximallyGraceful",{7,1}},"Planar"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyGraceful",{7,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyGraceful",{7,1}}]],10]

GraphPlot@RotateGraph[,{6,7}]

v=Join[{{0,0},{1,0},{2,0}},Rest@Subdivide[{1/2,0},{1/2,Sqrt[3]/2},4]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[3,2,1,7,2,5,1,6,2],e[6,5,4,1]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

PlanarGraphEmbeddings

GraphData[{"MaximallyGraceful",{7,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyGraceful",{7,1}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"MaximallyGraceful",{7,1}},{"RCN","CN"}]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"MaximallyGraceful",{7,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyGraceful",{7,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"MaximallyGraceful",{7,1}},"Circulant"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyGraceful",{7,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyGraceful",{7,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyGraceful",{7,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyGraceful",{7,1}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"MaximallyGraceful",{7,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyGraceful",{7,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyGraceful",{7,1}}&]

RootGraph[GraphData[{"MaximallyGraceful",{7,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyGraceful",{7,1}},"Halin"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyGraceful",{7,1}},"Rigid"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyGraceful",{7,1}},"Flexible"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyGraceful",{7,1}},"LCF"]

GraphData[{"MaximallyGraceful",{7,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyGraceful",{7,1}},"LCFSignature"]

GraphData[{"MaximallyGraceful",{7,1}},"LCFNotations"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"MaximallyGraceful",{7,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyGraceful",{7,1}}],Debug->True]//Timing

GraphData[{"MaximallyGraceful",{7,1}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyGraceful",{7,1}},"VertexList"],GraphData[{"MaximallyGraceful",{7,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyGraceful",{7,1}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyGraceful",{7,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyGraceful",{7,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"MaximallyGraceful",{7,1}},"Matchstick"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyGraceful",{7,1}},"Edges"]]

3D construction

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

3D All

GraphData[{"MaximallyGraceful",{7,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyGraceful",{7,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyGraceful",{7,1}},"Polyhedral"]

GraphData[{"MaximallyGraceful",{7,1}},"Graph",{"3D","Polyhedron"}]

{"MaximallyGraceful", {8, 1}}

Names

GraphData[{"MaximallyGraceful",{8,1}},"StandardName"]

GraphData[{"MaximallyGraceful",{8,1}},"StandardNames"]

Primary

GraphData[{"MaximallyGraceful",{8,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"MaximallyGraceful",{8,1}},"Graph","All"]//StyleGraphs

Construction from connected component

cc=GraphData[{"MaximallyGraceful",{8,1}},"ConnectedComponents","Name"]

GraphData[cc[[1]],"Graph","All"]

Select[%,(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]

gs=MyGraphUnion[#,"K1"]&/@GraphData[cc[[1]],"Graph","All"]

RecognizeGraph/@gs

Inexact

Select[GraphData[{"MaximallyGraceful",{8,1}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"MaximallyGraceful",{8,1}}]]

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{"MaximallyGraceful",{8,1}},"VertexList"],GraphData[{"MaximallyGraceful",{8,1}},"Edges"],GraphLayout->"TutteEmbedding"],{5,1}]

v={};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Degenerate

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"MaximallyGraceful",{8,1}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"MaximallyGraceful",{8,1}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"MaximallyGraceful",{8,1}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"MaximallyGraceful",{8,1}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"MaximallyGraceful",{8,1}},"Hamiltonian"]

GraphData[{"MaximallyGraceful",{8,1}},"LCF"]

GraphData[{"MaximallyGraceful",{8,1}},"HamiltonianCycleCount"]

Planar

GraphData[{"MaximallyGraceful",{8,1}},"Planar"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData[{"MaximallyGraceful",{8,1}}],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData[{"MaximallyGraceful",{8,1}}]],10]

PlanarGraphEmbeddings

GraphData[{"MaximallyGraceful",{8,1}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"MaximallyGraceful",{8,1}}],Debug->True])//Timing

Length[plemb]

MinimalCrossing

GraphData[{"MaximallyGraceful",{8,1}},{"RCN","CN"}]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalLocalCrossing

GraphData[{"MaximallyGraceful",{8,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"MaximallyGraceful",{8,1}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

Circulant

GraphData[{"MaximallyGraceful",{8,1}},"Circulant"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"MaximallyGraceful",{8,1}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"MaximallyGraceful",{8,1}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"MaximallyGraceful",{8,1}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"MaximallyGraceful",{8,1}},"ComplementGraph","Name"]

Line graph

GraphData[{"MaximallyGraceful",{8,1}},"Line"]

LineGraphQ[GraphData[{"MaximallyGraceful",{8,1}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"MaximallyGraceful",{8,1}}&]

RootGraph[GraphData[{"MaximallyGraceful",{8,1}}]]

RecognizeGraph[%]

Halin

GraphData[{"MaximallyGraceful",{8,1}},"Halin"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"MaximallyGraceful",{8,1}},"Rigid"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"MaximallyGraceful",{8,1}},"Flexible"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"MaximallyGraceful",{8,1}},"LCF"]

GraphData[{"MaximallyGraceful",{8,1}},"HamiltonianCycleCount"]

GraphData[{"MaximallyGraceful",{8,1}},"LCFSignature"]

GraphData[{"MaximallyGraceful",{8,1}},"LCFNotations"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

UnitDistance

GraphData[{"MaximallyGraceful",{8,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"MaximallyGraceful",{8,1}}],Debug->True]//Timing

GraphData[{"MaximallyGraceful",{8,1}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"MaximallyGraceful",{8,1}},"VertexList"],GraphData[{"MaximallyGraceful",{8,1}},"EdgeList"]],MaxIterations->500]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"MaximallyGraceful",{8,1}},"Graph",#]&/@{"All","UnitDistance"})

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"MaximallyGraceful",{8,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"MaximallyGraceful",{8,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"MaximallyGraceful",{8,1}},"Matchstick"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"MaximallyGraceful",{8,1}},"Edges"]]

3D construction

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

3D All

GraphData[{"MaximallyGraceful",{8,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"MaximallyGraceful",{8,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"MaximallyGraceful",{8,1}},"Polyhedral"]

GraphData[{"MaximallyGraceful",{8,1}},"Graph",{"3D","Polyhedron"}]

GraphData

AddIndexedClass

Most@data[[All,-1]]

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

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

RenameGraphFiles[]

GraphDataString

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

WriteString[file,GraphDataString[,
"StandardName"->{"MaximallyGraceful",{8,1}},
"Name"->"8\[Hyphen]maximally graceful graph 1",
"Information"->"MaximallyGracefulGraph",
"NotationRules"->{"MaximallyGracefulGraph"}
]]

Close[file]