Cossidente-Penttila Graph

Author

Eric W. Weisstein
February 25, 2025

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

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

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

Special cases

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

Embeddings

<<MathWorld`Graphs`

{"CossidentePenttila", 3} == "GewirtzGraph"

Names

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

GraphData[{"CossidentePenttila",3},"StandardNames"]

{"CossidentePenttila",5}

Names

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

GraphData[{"CossidentePenttila",5},"StandardNames"]

Primary

GraphData[{"CossidentePenttila",5}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"CossidentePenttila",5},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CossidentePenttila",5}]]

Default embedding

GraphPlot[Graph[GraphData[{"CossidentePenttila",5},"VertexList"],GraphData[{"CossidentePenttila",5},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData[{"CossidentePenttila",5},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"CossidentePenttila",5},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"CossidentePenttila",5},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"CossidentePenttila",5},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"CossidentePenttila",5},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"CossidentePenttila",5},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"CossidentePenttila",5},"Hamiltonian"]

GraphData[{"CossidentePenttila",5},"LCF"]

GraphData[{"CossidentePenttila",5},"HamiltonianCycleCount"]

Planar

GraphData[{"CossidentePenttila",5},"Planar"]

GraphData[{"CossidentePenttila",5},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"CossidentePenttila",5},{"RCN","CN"}]

GraphData[{"CossidentePenttila",5},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

(cn=CrossingNumber[GraphData[{"CossidentePenttila",5}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CossidentePenttila",5}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CossidentePenttila",5}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CossidentePenttila",5}],TimeConstraint->86400])//AbsoluteTiming

Quit

MinimalCrossing construction

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

(g=MinimalCrossingGraph[GraphData[{"CossidentePenttila",5}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

tuttegraphs=IGLayoutTutte[g,"OuterFace"->#]&/@faces

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",5},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",5},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",5},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CossidentePenttila",5}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}])//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",5},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",5},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",5},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"CossidentePenttila",5},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"CossidentePenttila",5},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"CossidentePenttila",5},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"CossidentePenttila",5},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"CossidentePenttila",5}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",5},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"CossidentePenttila",5}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",5},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"CossidentePenttila",5},"Circulant"]

GraphData[{"CossidentePenttila",5},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"CossidentePenttila",5},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"CossidentePenttila",5}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"CossidentePenttila",5},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"CossidentePenttila",5},"ComplementGraph","Name"]

Line graph

GraphData[{"CossidentePenttila",5},"Line"]

LineGraphQ[GraphData[{"CossidentePenttila",5}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"CossidentePenttila",5}&]

RootGraph[GraphData[{"CossidentePenttila",5}]]

RecognizeGraph[%]

Halin

GraphData[{"CossidentePenttila",5},"Halin"]

GraphData[{"CossidentePenttila",5},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"CossidentePenttila",5},"Rigid"]

GraphData[{"CossidentePenttila",5},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"CossidentePenttila",5},"Flexible"]

GraphData[{"CossidentePenttila",5},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"CossidentePenttila",5},"LCF"]

GraphData[{"CossidentePenttila",5},"HamiltonianCycleCount"]

GraphData[{"CossidentePenttila",5},"LCFSignature"]

GraphData[{"CossidentePenttila",5},"LCFNotations"]

GraphData[{"CossidentePenttila",5},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"CossidentePenttila",5}],TimeConstraint->120]

LCF compute 10^3

Tally[(lcf=LCF[GraphData[{"CossidentePenttila",5}],10^3])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"CossidentePenttila",5},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^4

Tally[(lcf=LCF[,10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"CossidentePenttila",5},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^5

Tally[(lcf=LCF[,10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"CossidentePenttila",5},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^6

Tally[(lcf=LCF[,10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"CossidentePenttila",5},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"CossidentePenttila",5},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CossidentePenttila",5}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CossidentePenttila",5}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CossidentePenttila",5},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

UnitDistance

GraphData[{"CossidentePenttila",5},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"CossidentePenttila",5}],Debug->True]//Timing

GraphData[{"CossidentePenttila",5},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"CossidentePenttila",5},"VertexList"],GraphData[{"CossidentePenttila",5},"EdgeList"]],MaxIterations->500]

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

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"CossidentePenttila",5}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

Matchstick

GraphData[{"CossidentePenttila",5},"Matchstick"]

GraphData[{"CossidentePenttila",5},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"CossidentePenttila",5},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"CossidentePenttila",5},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"CossidentePenttila",5},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"CossidentePenttila",5},"Polyhedral"]

GraphData[{"CossidentePenttila",5},"Graph",{"3D","Polyhedron"}]

{"CossidentePenttila", 7}

Names

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

GraphData[{"CossidentePenttila",7},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"CossidentePenttila",7}]]

Default embedding

GraphPlot[Graph[GraphData[{"CossidentePenttila",7},"VertexList"],GraphData[{"CossidentePenttila",7},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData[{"CossidentePenttila",7},"Hamiltonian"]

GraphData[{"CossidentePenttila",7},"LCF"]

GraphData[{"CossidentePenttila",7},"HamiltonianCycleCount"]

Planar

GraphData[{"CossidentePenttila",7},"Planar"]

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

MinimalCrossing

GraphData[{"CossidentePenttila",7},{"RCN","CN"}]

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

MinimalCrossingNumber

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

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

(cn=CrossingNumber[GraphData[{"CossidentePenttila",7}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CossidentePenttila",7}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CossidentePenttila",7}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"CossidentePenttila",7}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

(g=MinimalCrossingGraph[GraphData[{"CossidentePenttila",7}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

tuttegraphs=IGLayoutTutte[g,"OuterFace"->#]&/@faces

Select[tuttegraphs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",7},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",7},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",7},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"CossidentePenttila",7}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}])//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",7},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"CossidentePenttila",7},"V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",7},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"CossidentePenttila",7},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"CossidentePenttila",7},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"CossidentePenttila",7}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",7},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"CossidentePenttila",7}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"CossidentePenttila",7},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"CossidentePenttila",7},"Circulant"]

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

Circulant construction

GraphData[{"CossidentePenttila",7},"NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"CossidentePenttila",7},"Line"]

LineGraphQ[GraphData[{"CossidentePenttila",7}]]//Timing

RootGraph

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

RootGraph[GraphData[{"CossidentePenttila",7}]]

RecognizeGraph[%]

Halin

GraphData[{"CossidentePenttila",7},"Halin"]

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

Rigid

GraphData[{"CossidentePenttila",7},"Rigid"]

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

Flexible

GraphData[{"CossidentePenttila",7},"Flexible"]

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

LCF

GraphData[{"CossidentePenttila",7},"LCF"]

GraphData[{"CossidentePenttila",7},"HamiltonianCycleCount"]

GraphData[{"CossidentePenttila",7},"LCFSignature"]

GraphData[{"CossidentePenttila",7},"LCFNotations"]

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

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

LCF compute random

FindRandomLCFNotation[GraphData[{"CossidentePenttila",7}],TimeConstraint->120]

LCF compute 10^3

Tally[(lcf=LCF[GraphData[{"CossidentePenttila",7}],10^3])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"CossidentePenttila",7},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^4

Tally[(lcf=LCF[GraphData[{"CossidentePenttila",7}],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"CossidentePenttila",7},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"CossidentePenttila",7}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{{"CossidentePenttila",7},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"CossidentePenttila",7},"V"]]

Length[FindHamiltonianCycle[GraphData[{"CossidentePenttila",7}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"CossidentePenttila",7}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"CossidentePenttila",7},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

UnitDistance

GraphData[{"CossidentePenttila",7},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"CossidentePenttila",7},"Matchstick"]

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

3D default

Graph3D[GraphData[{"CossidentePenttila",7},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"CossidentePenttila",7},"Polyhedral"]

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

Properties

ChromaticNumber

5

GraphData[{"CossidentePenttila",5},"ChromaticNumber"]

GraphData[{"CossidentePenttila",5},"MaximalIndependentVertexSetCount"]

VertexChromaticNumber[GraphData[{"CossidentePenttila",5}]]//Timing

ChromaticNumber[GraphData[{"CossidentePenttila",5}],Method->{"ConicOptimization","Gurobi"},Debug->True]//Timing

7

GraphData[{"CossidentePenttila",7},"ChromaticNumber"]

GraphData[{"CossidentePenttila",7},"MaximalIndependentVertexSetCount"]

VertexChromaticNumber[GraphData[{"CossidentePenttila",7}]]//Timing

ChromaticNumber[GraphData[{"CossidentePenttila",7}],Method->{"ConicOptimization","Gurobi"},Debug->True]//Timing

Class1

GraphData[#,"Class1"]&/@GraphData["CossidentePenttila"]

EdgeChromaticNumber

5

GraphData[{"CossidentePenttila",5},"EdgeChromaticNumber"]

GraphData[{"CossidentePenttila",5},"Class1"]

EdgeChromaticNumber[GraphData[{"CossidentePenttila",5}]]//Timing

ChromaticNumber[GraphData[{"CossidentePenttila",5}],Method->{"ConicOptimization","Gurobi"},Debug->True]//Timing

7

GraphData[{"CossidentePenttila",7},"EdgeChromaticNumber"]

EdgeChromaticNumber[GraphData[{"CossidentePenttila",7}]]//Timing

...crash...

bug(415935): EdgeChromaticNumber[graphs on >~ 50000 edges] segfaults kernel

MyEdgeChromaticNumber[GraphData[{"CossidentePenttila",7}],Method->Automatic,Debug->True]//Timing

...crash...

bug(415935): EdgeChromaticNumber[graphs on >~ 50000 edges] segfaults kernel

MyEdgeChromaticNumber[GraphData[{"CossidentePenttila",7}],Method->"Blossom",Debug->True]//Timing

FindEdgeColoring[GraphData[{"CossidentePenttila",7}]]//Timing

...crash...

bug(415935): EdgeChromaticNumber[graphs on >~ 50000 edges] segfaults kernel

MyFindEdgeColoring[GraphData[{"CossidentePenttila",7}],Method->"FindIndependentEdgeSet",Debug->False]//Timing

MyFindEdgeColoring[GraphData[{"CossidentePenttila",7}],Method->"VizingClass1",Debug->True]//Timing

MaximumIndependentVertexSet

With[{gn={"CossidentePenttila",5}},{gn,MyFindIndependentVertexSet[GraphData[gn],Method->{"LinearOptimization","Gurobi"}]}]//Timing

MinimumDominatingSet

With[{gn={"CossidentePenttila",5}},{gn,FindDominatingSet[GraphData[gn],Method->"Gurobi"]}]//Timing

RegularParameters

TextGrid[Table[
{
q,
{(1/2) (1+q) (1+(q^3)),{(1/2) (-1+q) (1+(q^2))},{(1/2) (-3+q)},{(1/2) (((-1+q))^2)}},
GraphData[{"CossidentePenttila",q},"RegularParameters"]
},
{q,{3,5,7}}],
Dividers->All]

MinimumTotalDominatingSet

With[{gn={"CossidentePenttila",5}},{gn,FindTotalDominatingSet[GraphData[gn],Method->"Gurobi"]}]//Timing

VertexCount

TextGrid[Table[
{
q,
(1/2) (1+q) (1+(q^3)),
GraphData[{"CossidentePenttila",q},"VertexCount"]
},
{q,{3,5,7}}],
Dividers->All,Alignment->{Decimal}]

Construction

primepowers=Select[Range[1,200,2],PrimePowerQ]

primepowers==Select[Range[1,200,2],PrimeNu[#]==1&]

Print[{#,VertexCount[CossidentePenttilaGraph[#]]//Timing}]&/@Take[primepowers,5]

Vertex count:

(#^3+1)(#+1)/2&/@Prepend[primepowers,1]

Parameters

{(#^3+1)(#+1)/2,(#^2+1)(#-1)/2,(#-3)/2,(#-1)^2/2}&/@Take[primepowers,2]

Print[{
#,
Timing[g=CossidentePenttilaGraph[#]],
VertexCount[g],
{(#^3+1)(#+1)/2,(#^2+1)(#-1)/2,(#-3)/2,(#-1)^2/2},
RegularParameters[g],
RecognizeGraph[g]
}]&/@Take[primepowers,3]

GraphData["GewirtzGraph","RegularParameters"]

GraphData

AddIndexedClass

AddIndexedClass["CossidentePenttila",{"GewirtzGraph"->3},"14.3"]

RenameGraphFiles[]

GraphDataClassString

GraphDataClassString["CossidentePenttila"]

GraphDataString

CossidentePenttilaGraphs={{3,},{5,},{7,}};

file=OpenWrite["~/CossidentePenttila.m"]

WriteString[file,
GraphDataString[#2,
"StandardName"->{"CossidentePenttila",#},
"Name"->ToString[#2]<>"\[Hyphen]Cossidente\[Hyphen]Penttila graph",
"Embeddings"->None,
"Information"->"CossidentePenttilaGraph",
"NotationRules"->{"CossidentePenttila"->#},
"Classes"->{"CossidentePenttila","StronglyRegular"},
"RegularParameters"->{(#^3+1)(#+1)/2,{(#^2+1)(#-1)/2},{(#-3)/2},{(#-1)^2/2}},
"Skip"->{"ABCEnergy","ABCSpectralRadius","Arboricity","ArithmeticGeometricEnergy","ArithmeticGeometricSpectralRadius","Bandwidth","BurningNumber","Chord","Chords","ChromaticNumber","CliqueCoveringNumber","ConnectedDominatingSet","ConnectedInducedSubgraphPolynomial","ConstructionNumber","CoolingNumber","CyclicEdgeConnectivity","CyclicEdgeCuts","CyclicGroup","DetourPolynomial","DistinguishingNumber","EdgeBetweennessCentralities","EdgeChromaticNumber","EdgeCovers","EdgeCuts","Energy","ErdosSequence","EulerianCycles","FixingNumber","FractionalIndependenceNumber","HamiltonDecomposable","HamiltonianCycles","HamiltonianWalks","HouseOfGraphsID","IdiosyncraticPolynomial","IndependenceNumber","IndependencePolynomial","IntersectionNumber","IntersectionNumber","IrredundancePolynomial","LambdaComponents","LaplacianPolynomial","LongestCycle","LongestCycles","MaximalIndependentEdgeSet","MaximalIndependentEdgeSets","MaximalIndependentVertexSet","MaximalIndependentVertexSets","MaximalIndependencePolynomial","MaximumFlowMatrix","MaximumIndependentEdgeSetCount","MaximumIndependentEdgeSets","MinimumVertexColoring","MaximumIndependentVertexSet","MaximumIndependentVertexSetCount","MaximumIndependentVertexSets","MetricDimension","MinimumConnectedDominatingSet","MinimumCostFlowMatrix","MinimumEdgeColoring","MinimumCyclicEdgeCuts","MinimumDistinguishingLabelings","MinimumDominatingSet","MinimumPathCoverings","MinimumTotalDominatingSet","MinimumVertexCover","MinimumVertexCut","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","Minors","OddChordlessCycles","PathPolynomial","ProjectivePlanar","QuadraticEmbeddingConstant","RadioLabeling","RadioLabelings","RadioNumber","RandicEnergy","RectilinearCrossingCount","ResistanceMatrix","Skewness","SomborEnergy","SomborSpectralRadius","Thickness","TotalDominationPolynomial","Triameter","TuttePolynomial","UpperDominationNumber"},
TimeConstraint->10
]
]&@@@Drop[CossidentePenttilaGraphs,2];

Close[file]