Petersen Family

Author

Eric W. Weisstein
March 8, 2023

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

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

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

Source

https://en.wikipedia.org/wiki/Petersen_family

In graph theory, the Petersen family is a set of seven undirected graphs that includes the Petersen graph and the complete graph K6.

The Petersen family then consists of every graph that can be reached from the Petersen graph by a combination of Δ-Y and Y-Δ transforms. There are seven graphs in the family, including the complete graph K6 on six vertices, the eight-vertex graph formed by removing a single edge from the complete bipartite graph K4,4, and the seven-vertex complete tripartite graph K3,3,1.

Table

TextGrid[
Sort[{GraphData[#,"NotationRules","PetersenFamily"],GraphData[#,"V"],#}&/@GraphData["PetersenFamily"]],
Dividers->All]

Graphic

pfam=SortBy[
GraphData["PetersenFamily"],
{-GraphData[#,"V"],GraphData[#,"NotationRules","PetersenFamily"]}&
]

GraphicsGrid[Partition[
Show[
StyleGraphs[GraphData[#]],
PlotLabel->Column[{If[MissingQ[not=GraphData[#,"Notation"]],
Style[GraphData[#,"Name"],Italic],
not/.s_String?(StringMatchQ[#,LetterCharacter]&):>Style[s,Italic]/.Row[x_]:>Row[x," "]],Row[{Style["n",Italic]," == ",GraphData[#,"V"]}]},BaseStyle->Directive[Black,FontFamily->"Times",14],Alignment->Center]]&/@pfam,UpTo[4]],Dividers->All,ImageSize->700,Alignment->Top]

∇Y/Y∇

With[{dy=1/16,r=.06},GraphicsRow[{
Graph[{1,2,3},UndirectedEdge@@@Subsets[Range[3],{2}],VertexCoordinates->CirclePoints[{1,-Pi/2},3],VertexStyle->Black,VertexSize->{"Scaled",r},EdgeStyle->Black],
Graphics[{Arrowheads[.1],
Arrow[{{0,dy},{1,dy}}],Text["∇Y",{1/2,dy},{0,-1}],
Arrow[{{1,-dy},{0,-dy}}],Text["Y∇",{1/2,-dy},{0,1.3}]
},BaseStyle->Directive[24,FontFamily->"Times"]],
Graph[{1,2,3,4},UndirectedEdge@@@Table[{n,4},{n,3}],VertexCoordinates->Append[CirclePoints[{1,-Pi/2},3],{0,0}],VertexStyle->{Black,4->Red},VertexSize->{"Scaled",r},EdgeStyle->Black]
},ImageSize->500,Alignment->Center]
]

Embeddings

<<MathWorld`Graphs`

{"PetersenFamily", 1} == "PetersenGraph"

GraphData[{"PetersenFamily",1},"StandardName"]

{"PetersenFamily", 2}

GraphData[{"PetersenFamily",2},"StandardName"]

Primary

GraphData[{"PetersenFamily",2}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"PetersenFamily",2},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"PetersenFamily",2},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"PetersenFamily",2},"Edges"]

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

RecognizeGraph[g]

gs=Join[{g},{,}]

GraphPlot[GraphData[{"PetersenFamily",2},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

Degenerate

GraphData[{"PetersenFamily",2},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"PetersenFamily",2},"Graph","Degenerate"]

Bilateral

GraphData[{"PetersenFamily",2},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"PetersenFamily",2},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"PetersenFamily",2}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"PetersenFamily",2}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

Planar

GraphData[{"PetersenFamily",2},"Planar"]

GraphData[{"PetersenFamily",2},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"PetersenFamily",2},{"RCN","CN"}]

GraphData[{"PetersenFamily",2},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"PetersenFamily",2}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"PetersenFamily",2}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"PetersenFamily",2}],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData[{"PetersenFamily",2},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"PetersenFamily",2}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"PetersenFamily",2},"Circulant"]

GraphData[{"PetersenFamily",2},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"PetersenFamily",2},"Halin"]

GraphData[{"PetersenFamily",2},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"PetersenFamily",2},"Rigid"]

GraphData[{"PetersenFamily",2},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"PetersenFamily",2},"Flexible"]

GraphData[{"PetersenFamily",2},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"PetersenFamily",2},"LCF"]

GraphData[{"PetersenFamily",2},"HamiltonianCycleCount"]

GraphData[{"PetersenFamily",2},"LCFSignature"]

GraphData[{"PetersenFamily",2},"LCFNotations"]

GraphData[{"PetersenFamily",2},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"PetersenFamily",2},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"PetersenFamily",2}],Debug->True]//Timing

GraphData[{"PetersenFamily",2},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"PetersenFamily",2},"VertexList"],GraphData[{"PetersenFamily",2},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"PetersenFamily",2}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"PetersenFamily",2},"Matchstick"]

GraphData[{"PetersenFamily",2},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"PetersenFamily",2},"Edges"]]

3D All

GraphData[{"PetersenFamily",2},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"PetersenFamily",2},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"PetersenFamily",2},"Polyhedral"]

GraphData[{"PetersenFamily",2},"Graph",{"3D","Polyhedron"}]

{"PetersenFamily", 3}

GraphData[{"PetersenFamily",3},"StandardName"]

Primary

GraphData[{"PetersenFamily",3}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"PetersenFamily",3},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"PetersenFamily",3},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"PetersenFamily",3},"Edges"]

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

RecognizeGraph[g]

gs={,};

Degenerate

GraphData[{"PetersenFamily",3},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"PetersenFamily",3},"Graph","Degenerate"]

Bilateral

GraphData[{"PetersenFamily",3},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"PetersenFamily",3},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"PetersenFamily",3}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"PetersenFamily",3}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"PetersenFamily",3},"Planar"]

GraphData[{"PetersenFamily",3},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"PetersenFamily",3},{"RCN","CN"}]

GraphData[{"PetersenFamily",3},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"PetersenFamily",3}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"PetersenFamily",3}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"PetersenFamily",3}],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData[{"PetersenFamily",3},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"PetersenFamily",3}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"PetersenFamily",3},"Circulant"]

GraphData[{"PetersenFamily",3},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"PetersenFamily",3},"Halin"]

GraphData[{"PetersenFamily",3},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"PetersenFamily",3},"Rigid"]

GraphData[{"PetersenFamily",3},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"PetersenFamily",3},"Flexible"]

GraphData[{"PetersenFamily",3},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"PetersenFamily",3},"LCF"]

GraphData[{"PetersenFamily",3},"HamiltonianCycleCount"]

GraphData[{"PetersenFamily",3},"LCFSignature"]

GraphData[{"PetersenFamily",3},"LCFNotations"]

GraphData[{"PetersenFamily",3},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"PetersenFamily",3},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"PetersenFamily",3}],Debug->True]//Timing

GraphData[{"PetersenFamily",3},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"PetersenFamily",3},"VertexList"],GraphData[{"PetersenFamily",3},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"PetersenFamily",3}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

GraphPlot@RotateGraph[,{7,5}]

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

RecognizeGraph@g

Matchstick

GraphData[{"PetersenFamily",3},"Matchstick"]

GraphData[{"PetersenFamily",3},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"PetersenFamily",3},"Edges"]]

3D All

GraphData[{"PetersenFamily",3},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"PetersenFamily",3},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"PetersenFamily",3},"Polyhedral"]

GraphData[{"PetersenFamily",3},"Graph",{"3D","Polyhedron"}]

{"PetersenFamily", 4}

GraphData[{"PetersenFamily",4},"StandardName"]

Primary

GraphData[{"PetersenFamily",4}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"PetersenFamily",4},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"PetersenFamily",4},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{"PetersenFamily",4},"Edges"],Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{"PetersenFamily",4},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"PetersenFamily",4},"Graph","Degenerate"]

Bilateral

GraphData[{"PetersenFamily",4},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"PetersenFamily",4},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"PetersenFamily",4}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"PetersenFamily",4}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"PetersenFamily",4},"Planar"]

GraphData[{"PetersenFamily",4},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"PetersenFamily",4},{"RCN","CN"}]

GraphData[{"PetersenFamily",4},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"PetersenFamily",4}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"PetersenFamily",4}],TimeConstraint->10])//AbsoluteTiming

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"PetersenFamily",4}],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData[{"PetersenFamily",4},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"PetersenFamily",4}],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"PetersenFamily",4},"Circulant"]

GraphData[{"PetersenFamily",4},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"PetersenFamily",4},"Halin"]

GraphData[{"PetersenFamily",4},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"PetersenFamily",4},"Rigid"]

GraphData[{"PetersenFamily",4},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"PetersenFamily",4},"Flexible"]

GraphData[{"PetersenFamily",4},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"PetersenFamily",4},"LCF"]

GraphData[{"PetersenFamily",4},"HamiltonianCycleCount"]

GraphData[{"PetersenFamily",4},"LCFSignature"]

GraphData[{"PetersenFamily",4},"LCFNotations"]

GraphData[{"PetersenFamily",4},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"PetersenFamily",4},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"PetersenFamily",4}],Debug->True]//Timing

GraphData[{"PetersenFamily",4},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"PetersenFamily",4},"VertexList"],GraphData[{"PetersenFamily",4},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"PetersenFamily",4}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

Matchstick

GraphData[{"PetersenFamily",4},"Matchstick"]

GraphData[{"PetersenFamily",4},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"PetersenFamily",4},"Edges"]]

3D All

GraphData[{"PetersenFamily",4},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"PetersenFamily",4},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"PetersenFamily",4},"Polyhedral"]

GraphData[{"PetersenFamily",4},"Graph",{"3D","Polyhedron"}]

{"PetersenFamily", 5} == {"CompleteTripartite", {1, 3, 3}}

GraphData[{"PetersenFamily",5},"StandardName"]

{"PetersenFamily", 6} == {"Complete", 6}

GraphData[{"PetersenFamily",6},"StandardName"]

{"PetersenFamily", 7} == "K4,4-e"

GraphData[{"PetersenFamily",7},"StandardName"]

Construction

https://en.wikipedia.org/wiki/Petersen_family#Definition

The form of Δ-Y and Y-Δ transforms used to define the Petersen family is as follows:
	• If a graph G contains a vertex v with exactly three neighbors, then the Y-Δ transform of G at v is the graph formed by removing v from G and adding edges between each pair of its three neighbors.
	• If a graph H contains a triangle uvw, then the Δ-Y transform of H at uvw is the graph formed by removing edges uv, vw, and uw from H and adding a new vertex connected to all three of u, v, and w.

YDelta[g_Graph]:=Module[{p=Flatten[Position[VertexDegree[g],3]],adj=AdjacencyList[g]},
EdgeAdd[VertexDelete[g,#],UndirectedEdge@@@Subsets[#2,{2}]]&@@@Transpose[{p,adj[[p]]}]
]

DeltaY[g_Graph]:=Module[{tri=FindCycle[g,{3},All],n=VertexCount[g]+1},
Function[cyc,EdgeAdd[VertexAdd[EdgeDelete[g,cyc],n],UndirectedEdge@@@({#,n}&/@cyc[[All,1]])]]/@tri
]

YDeltaSequence[g_Graph,n_:Infinity]:=FixedPoint[DeleteDuplicates[Flatten[{#,YDeltaStep/@#}]]&,{CanonicalGraph[g]},n]
YDeltaStep[g_Graph]:=DeleteDuplicates[CanonicalGraph/@Flatten[{YDelta[g],DeltaY[g]}]]

petersenfamily1=YDeltaSequence[GraphData["P"]]

petersenfamily2=YDeltaSequence[GraphData["K6"]]

Sort[petersenfamily1]===Sort[petersenfamily2]

graphs=MapIndexed[{#,RecognizeGraph[#,"Cache"->"InternalOnly"],#2[[1]]}&,petersenfamily]

Tally[EdgeCount/@petersenfamily]

Tally[VertexCount/@petersenfamily]

rules=MapIndexed[RecognizeGraph[#]->#2[[1]]&,petersenfamily]

AddIndexedClass["PetersenFamily",rules,"13.3"]

RenameGraphFiles[]

Graphs

v=CirclePoints[{1,Pi/2},6];
ee=Join[Table[{i,i+3},{i,3}],Partition[Range[6],3,1,1][[All,{1,3}]]];
g=Graph[Range[Length[v]],UndirectedEdge@@@ee,VertexCoordinates->v,VertexLabels->Automatic]

<<MathWorld`Graphs`

RecognizeGraph[g]

GraphData

GraphDataString

file=OpenWrite["~/petersen-family.m"]

Cases[graphs,{gn_,{},n_}:>{gn,n}]

WriteString[file,GraphDataString[#,
"StandardName"->{"PetersenFamily",#2},
"Name"->ToString[#2]<>"\[Hyphen]Petersen family graph",
"Information"->"PetersenFamilyGraphs",
"Classes"->{"PetersenFamily"},
"NotationRules"->{"PetersenFamily"->#2}
]]&@@@Cases[graphs,{gn_,{},n_}:>{gn,n}]

Close[file]