Path Graph

Author

Eric W. Weisstein
June 1, 2025

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

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

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

Graphics

Built-in

GraphicsRow[Table[PathGraph[Range[n]],{n,4}]//StyleGraphs,Dividers->All]

Combinatorica

ShowGraphArray[Table[Path[n],{n,4}],VertexStyle->Disk[.05],VertexColor->Red]

PathGraph[n_]:=Module[{i},
{
Line[{{0,0},{0,1}}],
PointSize[.03],
Point/@Table[{0,i/(n-1)},{i,0,n-1}]
}
]

Show[GraphicsArray[Table[Graphics[PathGraph[n]],{n,2,5}]],
GraphicsSpacing->{-.7}]

PathGraphQ

<<MathWorld`Graphs`

DeleteCases[
{#,GraphData[#,"Path"],MyPathGraphQ[GraphData[#]]}&/@GraphData[All],
{_,x_,x_}
]//Timing

Properties

Acyclic

Table[GraphData[{"Path",n},"Acyclic"],{n,20}]

AdjacencyMatrixCount

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

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]//FunctionExpand

Table[Piecewise[{{1,n==1}},n!/2],{n,20}]

gf=x FindGeneratingFunction[seq,x]

Arboricity

Table[GraphData[{"Path",n},"Arboricity"],{n,20}]

ArcTransitive

Table[GraphData[{"Path",n},"ArcTransitive"],{n,20}]

ArcTransitivity

Table[GraphData[{"Path",n},"ArcTransitivity"],{n,20}]

AutomorphismCount

Table[GraphData[{"Path",n},"AutomorphismCount"],{n,20}]

BalabanIndex

Table[GraphData[{"Path",n},"BalabanIndex"],{n,10}]//FullSimplify

Bandwidth

Table[GraphData[{"Path",n},"Bandwidth"],{n,20}]

BridgeCount

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

Bridges

Table[GraphData[{"Path",n},"Bridges"],{n,4}]

Table[UndirectedEdge@@@Partition[Range[n],2,1],{n,4}]

BurningNumber

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

Table[Ceiling[Sqrt[n]],{n,20}]

%==seq

CharacteristicPolynomial

A049310

same as the MatchingPolynomial

(poly=Factor@Table[GraphData[{"Path",n},"CharacteristicPolynomial"][x],{n,k0=1,20}])//Column

CoefficientList[#,x]&/@Take[poly,10]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[ChebyshevU[n,-(x/2)],{n,k0,20}]

FullSimplify[poly2-poly]

poly3=Table[(-I)^n Fibonacci[n+1,-I x],{n,k0,20}]//Expand

FullSimplify[poly3-poly]

ChordCount

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

ChordlessCycleCount

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

ChromaticallyUnique

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

GraphData[{"ChromaticallyUnique","Path"}]

ChromaticInvariant

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

ChromaticNumber

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

ChromaticPolynomial

(poly=Factor@Table[GraphData[{"Path",n},"ChromaticPolynomial"][x],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(((x-1))^(n-1)) x,{n,20}]

FullSimplify[poly2-poly]

Circumference

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

Classes

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Path"])

CliqueCount

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

FindSequenceFunction[seq,n]

CliqueCoveringNumber

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

Table[Ceiling[n/2],{n,20}]

CliqueNumber

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

CliquePolynomial

(poly=Factor@Table[GraphData[{"Path",n},"CliquePolynomial"][x],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(1+x) (1+(-1+n) x),{n,20}]

FullSimplify[poly2-poly]

CochromaticGraphNames

Table[GraphData[{"Path",n},"CochromaticGraphNames"],{n,20}]//Column

ComplementOddChordlessCycleCount

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

ConnectedDominatingSetCount

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

ConnectedDominationNumber

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

FindSequenceFunction[seq,n]

ConnectedDominationPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Path",n},"ConnectedDominationPolynomial"][x],{n,k0=1,kmax=20}],_Missing[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

Binomial[n+1,2]

ConnectedInducedSubgraphPolynomial

(poly=DeleteCases[Factor@Table[GraphData[{"Path",n},"ConnectedInducedSubgraphPolynomial"][x],{n,k0=1,20}],_Missing[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[((x (n-n x+x ((x^n)-1)))/(((x-1))^2)),{n,20}]

FullSimplify[poly2-poly]

CrossingNumber

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

CycleCount

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

CyclePolynomial

(poly=Factor@Table[GraphData[{"Path",n},"CyclePolynomial"][x],{n,k0=1,20}])//Column

Cyclic

Table[GraphData[{"Path",n},"Cyclic"],{n,20}]

CyclomaticNumber

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

DetourIndex

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

FindSequenceFunction[seq,n]

Binomial[n+1,3]

FullSimplify[%-%7]

DetourMatrix

MatrixForm/@Table[GraphData[{"Path",n},"DetourMatrix"],{n,5}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,5}]

DetourPolynomial

A203993

Same as the distance polynomial

(poly=Factor@Table[GraphData[{"Path",n},"DetourPolynomial"][x],{n,k0=1,20}])//Column

CoefficientList[Take[poly,5],x]//Expand//Column

coef=Factor/@FindLinearRecurrence[poly]

CoefficientList[LinearRecurrence[{-4-5 x,-2 (2+6 x+5 (x^2)),-2 x (2+6 x+5 (x^2)),-(x^3) (4+5 x),-(x^5)},{-x,(-1+x) (1+x),-(2+x) (-2-2 x+(x^2)),(-6-4 x+(x^2)) (2+4 x+(x^2)),-(4+6 x+(x^2)) (-8-18 x-6 (x^2)+(x^3))},10],x]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

A204021:

(1/2)Table[(((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n),{n,10}]//Expand//ColumnForm

SeriesCoefficient[t*(1-x-x^2*t)/(1-2*t*(1-x)+t^2*x^2),{t,0,n}]

Table[(((-x))^n)ChebyshevT[2n,Sqrt[1/(2x)+1]],{n,5}]//Expand//Column

Subtract@@@Table[{(((-x))^n)ChebyshevT[2n,Sqrt[1/(2x)+1]],(1/2)((((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n))},{n,20}]//Simplify

Reverse of A100551 rows:

(1/2)Table[(((-(((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n)))/(Sqrt[1+2 x])),{n,5}]//Expand//Column

Table[(((-x))^(n-1)) ChebyshevU[n-1,1+1/x],{n,5}]//Expand//Column

Subtract@@@Table[{(((-x))^(n-1)) ChebyshevU[n-1,1+1/x],(1/2)(((-(((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n)))/(Sqrt[1+2 x]))},{n,20}]//Simplify

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(1/4) (2 (((-x))^n)+(((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n)+((n (-(((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n)))/(Sqrt[1+2 x]))),{n,20}]

FullSimplify[poly2-poly]

CoefficientList[Table[(1/4) (2 (((-x))^n)+(((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n)+((n (-(((-1-x-(Sqrt[1+2 x])))^n)+(((-1-x+(Sqrt[1+2 x])))^n)))/(Sqrt[1+2 x]))),{n,10}],x]//Flatten

poly3=Table[CharacteristicPolynomial[SparseArray[{i_,j_}:>Abs[i-j],n],x],{n,20}]

FullSimplify[poly-poly3]

CoefficientList[Table[CharacteristicPolynomial[SparseArray[{i_,j_}:>Abs[i-j],n],x],{n,10}],x]

Table[(1/4) (2 (((-x))^n)+2(((-x))^n)ChebyshevT[2n,Sqrt[1/(2x)+1]]+2n(((-x))^(n-1)) ChebyshevU[n-1,1+1/x]),{n,5}]//Expand//Normal

CoefficientList[%,x]

FullSimplify[(1/4) (2 (((-x))^n)+2(((-x))^n)ChebyshevT[2n,Sqrt[1/(2x)+1]]+2n(((-x))^(n-1)) ChebyshevU[n-1,1+1/x])]

CoefficientList[Table[(((((-x))^n) (x+x ChebyshevT[2 n,(Sqrt[1+(1/(2 x))])]-n ChebyshevU[n-1,1+(1/x)]))/(2 x)),{n,10}],x]

Diameter

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

DistanceMatrix

MatrixForm/@Table[GraphData[{"Path",n},"DistanceMatrix"],{n,5}]

MatrixForm/@Table[SparseArray[{i_,j_}:>Abs[i-j],n],{n,5}]

DistancePolynomial

A203993

Same as the DetourPolynomial

(poly=Factor@Table[GraphData[{"Path",n},"DistancePolynomial"][x],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

DistinguishingNumber

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

DomaticNumber

Table[DomaticNumber[g=PathGraph[Range[n]],FindDominatingSet[g,Infinity,All]],{n,8}]

DominatingSetCount

A000213: Tribonacci numbers

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

FindLinearRecurrence[seq]

LinearRecurrence[{1,1,1},{1,3,5},20]

FindSequenceFunction[seq,n]

Table[((Root[-1-#1-((#1)^2)+((#1)^3)&,1])^n) Root[-1+3 #1-11 ((#1)^2)+11 ((#1)^3)&,1]+((Root[-1-#1-((#1)^2)+((#1)^3)&,2])^n) Root[-1+3 #1-11 ((#1)^2)+11 ((#1)^3)&,2]+((Root[-1-#1-((#1)^2)+((#1)^3)&,3])^n) Root[-1+3 #1-11 ((#1)^2)+11 ((#1)^3)&,3],{n,20}]//FullSimplify

gf=x FindGeneratingFunction[seq,x]

Simplify[SeriesCoefficient[gf,{x,0,n}],n>0]//FullSimplify

DominationNumber

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

Table[Floor[(n+2)/3],{n,20}]

DominationPolynomial

A212633

(poly=Factor@Table[GraphData[{"Path",n},"DominationPolynomial"][x],{n,k0=1,20}])//Column

Take[poly,5]//Expand//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

Expand[%]

CoefficientList[LinearRecurrence[{x,x,x},{1,2+x,1+3 x+(x^2)},10],x]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

EdgeChromaticNumber

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

EdgeConnectivity

Table[GraphData[{"Path",n},"EdgeConnectivity"],{n,20}]

EdgeCount

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

EdgeCoverCount

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

FindSequenceFunction[seq,n]//FullSimplify

Table[Fibonacci[n-1],{n,20}]

EdgeCoverNumber

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

Table[Piecewise[{{0,n==1}},Ceiling[n/2]],{n,20}]

%==seq

EdgeCoverPolynomial

A284938

(poly=Factor@Table[GraphData[{"Path",n},"EdgeCoverPolynomial"][x],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

Prepend[CoefficientList[LinearRecurrence[{x,x},{0,x},{2,10}],x],{0}]//Flatten

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Related to Voyce-Morgan polynomials

Table[Sum[(x^(k+1)) Binomial[k,n-k-2],{k,0,n}],{n,10}]

Table[Sum[(x^(k+1)) Binomial[k,n-2-k],{k,0,n-2}],{n,10}]

Table[Sum[(x^(k+1)) Binomial[k,n-2-k],{k,1,n}],{n,10}]//Column

Simplify[(x^((n-1/2)-1))(x^(-n/2+1/2+1))]

Table[(x^(n/2))Fibonacci[n-1,(Sqrt[x])],{n,10}]

Prepend[CoefficientList[Table[(x^(n/2))Fibonacci[n-1,(Sqrt[x])],{n,2,14}],x],{0}]//Flatten

Table[(x^(n/2))Fibonacci[n-1,(Sqrt[x])],{n,10}]//Expand//Column

CoefficientList[Table[(x^(n/2))Fibonacci[n-1,(Sqrt[x])],{n,14}],x]//Column

CoefficientList[Table[ (x^(n/2))Fibonacci[n-1,(Sqrt[x])],{n,10}],x]

CoefficientList[Table[(I^n) (x^(n/2))Fibonacci[n-1,-I(Sqrt[x])],{n,14}],x]//Column

FullSimplify[(-I)^n Fibonacci[n+1,-I x]-ChebyshevU[n,-(x/2)],n∈Integers]

FullSimplify[FunctionExpand[%],n∈Integers]

Fibonacci[n-1, x]==ChebyshevU[n-2,(x/(2I))]/(((-I))^(n-2))

Table[{Fibonacci[n-1,(Sqrt[ x])],ChebyshevU[n-2,((Sqrt[x])/(2I))]/(((-I))^(n-2)) },{n,5}]//Expand

FullSimplify[(x^(n/2))ChebyshevU[n-2,((Sqrt[x])/(2I))]/(((-I))^(n-2)) ,n∈Integers]

Table[-(I^n) (x^(n/2)) ChebyshevU[-2+n,-((I (Sqrt[x]))/2)],{n,10}]//Expand//Column

Prepend[CoefficientList[Table[-(x^(n/2)) ChebyshevU[n-2,((Sqrt[x])/2)],{n,2,14}],x],{0}]//Flatten

Take[poly,10]//Expand

Table[(n+k)!/((n-k)!*(2*k)!),{n,-1,10},{k,0,n}]

poly2=Table[Sum[(x^(k+1)) Binomial[k,n-k-2],{k,0,n-2}],{n,k0,20}]

FullSimplify[poly2-poly]

Sum[(x^(k+1)) Binomial[k,n-k-2],{k,n}]

Table[ HypergeometricPFQ[{1,2,3-n},{(5/2)-(n/2),3-(n/2)},-(x/4)],{n,10}]

poly3=Table[(x^(n/2))Fibonacci[n-1,(Sqrt[x])],{n,20}]

Expand[poly3]

FullSimplify[poly-poly3]

EulerianCycleCount

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

FaceCount

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

FibonacciCube

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

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

FlowPolynomial

(poly=Factor@Table[GraphData[{"Path",n},"FlowPolynomial"][x],{n,k0=1,20}])//Column

FractionalChromaticNumber

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

FractionalEdgeChromaticNumber

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

Girth

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

Gonality

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

HamiltonConnected

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

HamiltonDecompositionCount

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

Hamiltonian

Table[GraphData[{"Path",n},"Hamiltonian"],{n,20}]

HamiltonianCycleCount

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

HamiltonianNumber

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

HamiltonianPathCount

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

HamiltonianWalkCount

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

HararyIndex

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

FindSequenceFunction[seq,n]//FullSimplify

HexagonCount

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

IdiosyncraticPolynomial

(poly=Factor@Table[GraphData[{"Path",n},"IdiosyncraticPolynomial"][x,y],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

IndependenceNumber

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

Table[Ceiling[n/2],{n,20}]

IndependencePolynomial

A011973

Same as matching-generating polynomial but with -> n + 1

(poly=Factor@Table[GraphData[{"Path",n},"IndependencePolynomial"][x],{n,k0=1,20}])//Column

Take[poly,10]//Expand//Column

Table[Fibonacci[n+2,x],{n,10}]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

CoefficientList[LinearRecurrence[{1,x},{1+x,1+2x},{-1,10}],x]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[Fibonacci[n+2,1/Sqrt[x]] (x^((n+1)/2)),{n,20}]

CoefficientList[Table[(x^((n-1)/2))Fibonacci[n,1/Sqrt[x]],{n,15}],x]

FullSimplify[poly2-poly]

IndependenceRatio

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

Table[Ceiling[n/2]/n,{n,20}]

IndependentEdgeSetCount

A000045

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

FindSequenceFunction[seq,n]

Table[Fibonacci[n+1],{n,20}]

IndependentVertexSetCount

A000045

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

Fibonacci[Range[20]+2]

FindGeneratingFunction[Fibonacci[Range[0,20]],x]

CoefficientList[Series[-(x/(-1+x+(x^2))),{x,0,20}],x]

IntersectionNumber

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

IrredundantSetCount

A286887

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

Table[Length[IrredundantSets[PathGraph[Range[n]]]],{n,12}]//Timing

seq={2,3,5,9,15,26,44,76,130,223,382,655,1123,1925,3300,5657,9698,16625,28500,48857,83755,143580,246137,421949,723341,1240013,2125736,3644118,6247058,10709240,18358693,31472038,53952053,92489213,158552901,271804912,465951173};

FindLinearRecurrence[seq]

LinearRecurrence[{1,1,0,1,0,-1},{2,3,5,9,15,26},20]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[((2+x+(x^3)-(x^4)-(x^5))/(1-x-(x^2)-(x^4)+(x^6))),{x,0,20}],x]

res=Refine[SeriesCoefficient[gf,{x,0,n}],n>0]

terms=List@@res;

N[terms/.n->0]//Chop

N[terms[[All,1]]/.n->1]

t1=terms[[1]]/.n->0

terms[[1]]

RootApproximant[t1,8]

r1=RootApproximant[N[t1,50],8]

N[t1-r1,1000]

RootApproximant[N[terms/.n->0,50],8]

Table[Sum[((Root[1-((#1)^2)-((#1)^4)-((#1)^5)+((#1)^6)&,k])^n)Root[1-32 #1+432 ((#1)^2)-950 ((#1)^3)-992 ((#1)^4)-89653 ((#1)^5)+89653 ((#1)^6)&,k/.{5->6,6->5}],{k,6}],{n,6}]//N//Chop

f1=1-((#1)^2)-((#1)^4)-((#1)^5)+((#1)^6)&;
f2=1-32 #1+432 ((#1)^2)-950 ((#1)^3)-992 ((#1)^4)-89653 ((#1)^5)+89653 ((#1)^6)&;

an=ToNumberField[Root[f2,#],Root[f1,#/.{5->6,6->5}]]&/@Range[6]

coef=Last/@an

SameQ@@coef

rs=RootSum[1-((#1)^2)-((#1)^4)-((#1)^5)+((#1)^6)&,((#)^n)((3191/89653)+(4752/89653)#-(4234/89653)((#)^2)+(11985/89653)((#)^3)-(2369/89653)((#)^4)+(3536/89653)((#)^5))&]

Table[((RootSum[1-((#)^2)-((#)^4)-((#)^5)+((#)^6)&,3191 ((#)^n)+4752 ((#)^(n+1))-4234 ((#)^(n+2))+11985 ((#)^(n+3))-2369 ((#)^(n+4))+3536 ((#)^(n+5))&])/89653),{n,20}]

KirchhoffIndex

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

FindSequenceFunction[seq,n]

Binomial[n+1,3]

KirchhoffSumIndex

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

FindSequenceFunction[seq,n]

Binomial[n,2]

LaplacianMatrix

MatrixForm/@Table[GraphData[{"Path",n},"LaplacianMatrix"],{n,10}]

MatrixForm/@Table[SparseArray[{{1,1}->1,{n,n}->1,Band[{1,2}]->-1,Band[{2,1}]->-1,Band[{1,1}]->2,Band[{1,2}]->-1,{2,n}->-1,{n,2}->1},{n,n}],{n,2,10}]

LaplacianPolynomial

A285072

A053122 with row-leading 0s and differing signs

CoefficientList[Table[CharacteristicPolynomial[KirchhoffMatrix[PathGraph[Range[n]]],x],{n,10}],x]//Flatten

(poly=Factor@Table[GraphData[{"Path",n},"LaplacianPolynomial"][x],{n,k0=1,20}])//Column

Take[poly,5]//Expand//Column

Table[(((-1))^(n+1))(x^(1/2))ChebyshevU[2n-1,-(Sqrt[x])/2],{n,5}]//Expand//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

LinearRecurrence[{2-x,-1},{-x,(-2+x) x},10]//Column

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(((-1))^(n+1))(x^(1/2))ChebyshevU[2n-1,-(Sqrt[x])/2],{n,20}]//Expand

FullSimplify[poly2-poly]

CoefficientList[Table[(((-1))^(n+1))(x^(1/2))ChebyshevU[2n-1,-(Sqrt[x])/2],{n,10}],x]//Flatten

poly3=Table[(((2^(-n)) ((((2-(Sqrt[-4+x]) (Sqrt[x])-x))^n)-(((2+(Sqrt[-4+x]) (Sqrt[x])-x))^n)))/(Sqrt[((-4+x)/x)])),{n,20}]//Expand//FullSimplify

FullSimplify[poly3-poly]

LeafCount

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

LongestCycleCount

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

LovaszNumber

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

LucasCube

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

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

MatchingGeneratingPolynomial

A011973

Same as independence polynomial but with n + 1 -> n

(poly=Factor@Table[GraphData[{"Path",n},"MatchingGeneratingPolynomial"][x],{n,k0=1,20}])//Column

Take[poly,10]//Expand//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[(x^(n/2))Fibonacci[n+1,1/Sqrt[x]],{n,20}]//Expand

FullSimplify[poly2-poly]

poly3=Table[(((-x))^(n/2))ChebyshevU[n,1/(2(Sqrt[-x]))],{n,20}]//Expand

FullSimplify[poly3-poly]

1/Sqrt[-1]

poly4=Table[(I^n)(x^(n/2))ChebyshevU[n,-I/(2(Sqrt[x]))],{n,20}]//Expand

FullSimplify[poly4-poly]

MatchingNumber

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

Table[Floor[n/2],{n,20}]

MatchingPolynomial

Same as the charactersitic polynomial

A049310

(poly=Factor@Table[GraphData[{"Path",n},"MatchingPolynomial"][x],{n,k0=1,20}])//Column

CoefficientList[Take[poly,10],x]//Column

Take[poly,8]//Expand//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[ChebyshevU[n,(x/2)],{n,20}]

FullSimplify[poly2-poly]

MaximalCliqueCount

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

MaximalIndependentEdgeSetCount

A000931: Padovan numbers

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

Table[Sum[Binomial[k,n-2k],{k,0,Floor[n/2]}],{n,3,22}]

Sum[Binomial[k,n-2k],{k,0,Floor[n/2]}]//FullSimplify

7->2,8->3

FindLinearRecurrence[Rest@seq]

LinearRecurrence[{0,1,1},{1,1,2},20]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]

f1=-1-#1+((#1)^3)&;
f2=-1+2 #1-23 ((#1)^2)+23 ((#1)^3)&;
pos={1,2,3};

Table[Sum[((Root[f1,k])^(n-1))Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

RootSum[f1,Evaluate[((#)^n) #^Range[0,Length[pos]-1].an[[1,2]]]&]

Table[Piecewise[{{0,n==1}},RootSum[-1-#1+((#1)^3)&,7 ((#1)^(n-1))+10 ((#1)^n)+((#1)^(n+1))&]/23],{n,20}]

gf=x FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>0]

MaximalIndependentVertexSetCount

A000931: Padovan numbers

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

LinearRecurrence[{0,1,1},{1,2,2},20]

FindSequenceFunction[seq,n]

f1=-1-#1+((#1)^3)&;
f2=-1+2 #1-23 ((#1)^2)+23 ((#1)^3)&;

pos={1,2,3};

Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

RootSum[f1,Evaluate[((#)^n) #^Range[0,Length[pos]-1].an[[1,2]]]&]

Table[RootSum[-1-#1+((#1)^3)&,7 ((#1)^n)+10 ((#1)^(n+1))+((#1)^(n+2))&]/23,{n,20}]

MaximalIrredundantSetCount

A291055

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

seq={1,2,2,4,6,8,13,17,27,40,57,86,122,184,269,395,582,849,1255,1843,2708,3982,5841,8597,12631,18566,27286,40082,58929,86598,127279,187052,274872,404001,593732,872606,1282416,1884660,2769856,4070718,5982611,8792345};

Table[GraphData[{"Path",n},"IrredundantSets"],{n,4}]//Column

Table[GraphData[{"Path",n},"MaximalIrredundantSets"],{n,4}]//Column

Table[Length[MaximalSets@IrredundantSets[PathGraph[Range[n]]]],{n,12}]//Timing

coef=FindLinearRecurrence[seq]

Take[seq,Length@coef]

LinearRecurrence[{0,1,1,1,1,0,-1,-2,-1,2,1,0,0,-1},{1,2,2,4,6,8,13,17,27,40,57,86,122,184},20]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

gf=((x (1+2 x+(x^2)+(x^3)+(x^4)-(x^5)-(x^6)-2 (x^7)+3 (x^9)-(x^12)-(x^13)))/(1-(x^2)-(x^3)-(x^4)-(x^5)+(x^7)+2 (x^8)+(x^9)-2 (x^10)-(x^11)+(x^14)));

Series[gf,{x,0,10}]

res=Refine[SeriesCoefficient[gf,{x,0,n}],n>0]

terms=List@@res;

Table[N[terms]//Chop,{n,-2,2}]

approx=RootApproximant[N[exact=terms/.n->0,300],14]

pos=approx[[All,-2]]

pos={1,2,3,4,13,14,10,9,5,6,12,11,7,8};

N[approx-exact,300]

f1=1-((#1)^3)-2 ((#1)^4)+((#1)^5)+2 ((#1)^6)+((#1)^7)-((#1)^9)-((#1)^10)-((#1)^11)-((#1)^12)+((#1)^14)&;
f2=1-177 #1+15088 ((#1)^2)-1021178 ((#1)^3)+57385005 ((#1)^4)-2148282502 ((#1)^5)+37324215197 ((#1)^6)-365575989898 ((#1)^7)+3274182693202 ((#1)^8)-18060885154737 ((#1)^9)+52392949294599 ((#1)^10)-1971553290516533 ((#1)^11)+8914414943034866 ((#1)^12)-47617929706047629 ((#1)^13)+47617929706047629 ((#1)^14)&;

Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

(an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@{1})//Timing

RootSum[f1,Evaluate[((#)^(n+Range[Length[pos]]-1)).an[[1,2]]]&]

Table[RootSum[1-#^3-2 #^4+#^5+2 #^6+#^7-#^9-#^10-#^11-#^12+#^14&,-4480566127993567 #^n+2115784835595702 #^(n+1)-8803686900182082 #^(n+2)+12438105918248674 #^(n+3)+9975829435558087 #^(n+4)+32647411155695559 #^(n+5)+921201586573742 #^(n+6)-12400355965941932 #^(n+7)-18709447182799197 #^(n+8)-16194871035876814 #^(n+9)-8478829128434826 #^(n+10)-3824486277258301 #^(n+11)+902031297001609 #^(n+12)+11119370357865554 #^(n+13)&]/333325507942333403,{n,20}]

MaximumCliqueCount

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

MaximumIndependentEdgeSetCount

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

Table[Piecewise[{{1,Mod[n,2]==0},{(n+1)/2,Mod[n,2]==1}}],{n,20}]

%==seq

MaximumIndependentVertexSetCount

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

Table[Piecewise[{{1+n/2,Mod[n,2]==0},{1,Mod[n,2]==1}}],{n,20}]

%==seq

MaximumLeafNumber

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

MaximumVertexDegree

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

MeanDistance

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

FindSequenceFunction[seq,n]

MinimalDominatingSetCount

A253412

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

CoefficientList[Series[((1+2 x+(x^2)+(x^3)-(x^4)-(x^5))/(1-(x^2)-(x^3)-(x^4)+(x^6))),{x,0,20}],x]

res=Refine[SeriesCoefficient[gf,{x,0,n}],n>0]

res=(((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1])^n) (-1+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1])^3)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1])^4)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1])^5)))/((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]))+(((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2])^n) (-1+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2])^3)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2])^4)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2])^5)))/((-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]))+(((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3])^n) (-1+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3])^3)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3])^4)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3])^5)))/((-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]))+(((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4])^n) (-1+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4])^3)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4])^4)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4])^5)))/((-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]))+(((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5])^n) (-1+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5])^3)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5])^4)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5])^5)))/((-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]) (Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]))+(((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6])^n) (-1+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6])^3)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6])^4)+((Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6])^5)))/((-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,1]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,2]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,3]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,4]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]) (-Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,5]+Root[1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&,6]));

terms=List@@res;

N[terms/.n->0]//Chop

approx=RootApproximant[N[exact=terms/.n->0,200],6]

N[approx-exact,200]

f1=1-((#1)^2)-((#1)^3)-((#1)^4)+((#1)^6)&;
f2=1-44 #1+714 ((#1)^2)-4809 ((#1)^3)+10763 ((#1)^4)-52441 ((#1)^5)+52441 ((#1)^6)&;

pos=approx[[All,-2]]

Table[Sum[((Root[f1,k])^n)Root[f2,pos[[k]]],{k,Length[pos]}],{n,10}]//N//Chop

an=ToNumberField[Root[f2,pos[[#]]],Root[f1,#]]&/@Range[Length[pos]]

Equal@@Last/@an

an[[1,2]]

RootSum[f1,Evaluate[((#)^n) #^Range[0,Length[pos]-1].an[[1,2]]]&]

Table[RootSum[1-((#)^2)-((#)^3)-((#)^4)+((#)^6)&,9 ((#)^n)-18 ((#)^(n+2))+23 ((#)^(n+3))-3 ((#)^(n+4))+32 ((#)^(n+5))&]/229,{n,20}]

MinimalEdgeCoverCount

Padovan numbers

A000931

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n-1]

Table[RootSum[-1-#+((#)^3)&,-11 ((#)^(n+4))+4 ((#)^(n+5))+5 ((#)^(n+6))&]/23,{n,20}]

MinimalEdgeCoverSignature

seq=Table[GraphData[{"Path",n},"MinimalEdgeCoverSignature"],{n,20}]//Column

MinimumCliqueCoveringCount

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

Table[Piecewise[{{1,n==1},{1,Mod[n,2]==0},{(n-1)/2,Mod[n,2]==1}}],{n,20}]

MinimumConnectedDominatingSetCount

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

FindSequenceFunction[DeleteCases[seq,_Missing],n]

MinimumDistinguishingLabelingCount

A233411

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

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n-1]//FullSimplify

Table[Piecewise[{{1,n==1}},2^n-2^Ceiling[n/2]],{n,20}]

%==seq

MinimumDominatingSetCount

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

seq[[1;;All;;3]]

Table[n(n+3)/2-1,{n,7}]

Table[(n(n+3)/2-1)/.n->(k+2)/3,{k,1,20,3}]

(n(n+3)/2-1)/.n->(k+2)/3//Factor

seq[[2;;All;;3]]

seq[[3;;All;;3]]

Table[Piecewise[{{1,Mod[n,3]==0},{(1/18) (n^2+13n+4),Mod[n,3]==1},{(n+4)/3,Mod[n,3]==2}}],{n,20}]

%==seq

MinimumEdgeCoverCount

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

Table[Piecewise[{{1,Mod[n,2]==0},{(n-1)/2,Mod[n,2]==1}}],{n,20}]

%==seq

MinimumVertexDegree

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

MolecularTopologicalIndex

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

FindSequenceFunction[seq,n]

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

Table[Piecewise[{{0,n==1}},(1/3) (2 (n^3)-3n^2+13n-18)],{n,20}]

gf=x FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>0]

Nonhamiltonian

Table[GraphData[{"Path",n},"Nonhamiltonian"],{n,20}]

NormalizedLaplacianMatrix

MatrixForm/@(m1=Table[GraphData[{"Path",n},"NormalizedLaplacianMatrix"],{n,6}])

MatrixForm/@Table[SparseArray[{{n_,n_}->1,{1,2}->-1/(Sqrt[2]),{2,1}->-1/(Sqrt[2]),{n-1,n}->-1/(Sqrt[2]),{n,n-1}->-1/(Sqrt[2]),Band[{1,2}]->-1/2,Band[{2,1}]->-1/2},n],{n,2,6}]

m2=Table[Piecewise[{{{{0}},n==1},{{{1,-1},{-1,1}},n==2}},SparseArray[{{k_,k_}->1,{1,2}->-1/Sqrt[2],{2,1}->-1/Sqrt[2],{n-1,n}->-1/Sqrt[2],{n,n-1}->-1/Sqrt[2],Band[{1,2}]->-1/2,Band[{2,1}]->-1/2},n]],{n,6}]

Union[Flatten[#]]&/@Normal[m1-m2]

OddChordlessCycleCount

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

PathCount

A287988

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[DeleteMissing@seq,n]

Binomial[n,2]

PathPolynomial

(poly=Factor[Table[GraphData[{"Path",n},"PathPolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

p=.

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

Pell

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

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

PentagonCount

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

Perfect

Table[GraphData[{"Path",n},"Perfect"],{n,20}]

ProjectivePlaneCrossingNumber

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

Radius

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

Table[Floor[n/2],{n,20}]

RankPolynomial

(poly=Factor@Table[GraphData[{"Path",n},"RankPolynomial"][x,y],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

RectilinearCrossingNumber

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

Skewness

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

SpanningTreeCount

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

SquareCount

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

StabilityIndex

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

Table[Piecewise[{{Fibonacci[n+1],Mod[n,2]==0},{0,Mod[n,2]==1}}],{n,20}]

TopologicalIndex

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

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

ToroidalCrossingNumber

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

Traceable

Table[GraphData[{"Path",n},"Traceable"],{n,20}]

TriangleCount

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

TuttePolynomial

(poly=Factor@Table[GraphData[{"Path",n},"TuttePolynomial"][x,y],{n,k0=1,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,20}]

FullSimplify[poly2-poly]

Untraceable

Table[GraphData[{"Path",n},"Untraceable"],{n,20}]

VertexConnectivity

Table[GraphData[{"Path",n},"VertexConnectivity"],{n,20}]

VertexCoverNumber

Related to but not the same as IndependenceNumber

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

Table[Floor[n/2],{n,20}]

VertexCount

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

FindSequenceFunction[seq,n]

VertexCoverPolynomial

A030528

(poly=Factor@Table[GraphData[{"Path",n},"VertexCoverPolynomial"][x],{n,k0=1,20}])//Column

Take[poly,10]//Expand//Column

CoefficientList[Take[poly,10],x]//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[(z^k0)FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

(poly2=Table[(((-I))^(n+1))(x^((n-1)/2))ChebyshevU[n+1,I (Sqrt[x])/2],{n,20}])//Expand//Column

FullSimplify[poly2-poly]

(poly3=Table[x^((n-1)/2) Fibonacci[n+2,Sqrt[x]],{n,20}])//Expand//Column

FullSimplify[poly3-poly]

CoefficientList[Table[x^(n/2-1)Fibonacci[n+1,Sqrt[x]],{n,10}],x]//Flatten

Sum[Binomial[k,n-k](x^(k-1)),{k,n}]//FullSimplify

Table[Binomial[1,-1+n] HypergeometricPFQ[{1,2,1-n},{(3/2)-(n/2),2-(n/2)},-(x/4)],{n,5}]

...wrong...

Table[Sum[Binomial[k,n-k](x^(k-1)),{k,n}],{n,5}]

VertexDegrees

seq=Table[GraphData[{"Path",n},"VertexDegrees"],{n,5}]

WienerIndex

A000292

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

FindSequenceFunction[seq,n]//Factor

Table[n(n^2-1)/6,{n,10}]

FindLinearRecurrence[seq]

LinearRecurrence[{4,-6,4,-1},{0,1,4,10},20]

gf=x FindGeneratingFunction[seq,x]

CoefficientList[Series[(x/(((-1+x))^4)),{x,0,20}],x]

Binomial[Range[20]+1, 3]

WienerSumIndex

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

FindSequenceFunction[seq,n]

Binomial[n,2]

Embedding types

PathGraph default

GraphicsGrid[Partition[Table[PathGraph[Range[n]],{n,25}]//StyleGraphs,5],Dividers->All]

"CircularEmbedding"

GraphicsGrid[Partition[Table[MyPathGraph[n,GraphLayout->"CircularEmbedding"],{n,15}]//StyleGraphs,5],Dividers->All]

"LinearEmbedding"

GraphicsGrid[Partition[Table[MyPathGraph[n,GraphLayout->"LinearEmbedding"],{n,10}]//StyleGraphs,5],Dividers->All]

"SpiralEmbedding"

GraphicsGrid[Partition[Table[MyPathGraph[n,GraphLayout->"SpiralEmbedding"],{n,25}]//StyleGraphs,5],Dividers->All]

"ZigZagEmbedding"

GraphicsGrid[Partition[Table[MyPathGraph[n,GraphLayout->"ZigZagEmbedding"],{n,10}]//StyleGraphs,5],Dividers->All]

Embeddings

<<MathWorld`Graphs`

{"Path", 1} == "SingletonGraph"

Names

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

GraphData[{"Path",1},"StandardNames"]

{"Path", 2}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

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

GraphData[{"Path",2},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",2},"Graph","Perspective"]//StyleGraphs

Perspective construction

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

HoneycombToroidal construction

GraphData[{"Path",2},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=2},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",2}}]]//Timing

g=GeneralizedHoneycombGraph[2,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",2},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",2},"Graph","IGraph"]//StyleGraphs

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

Circulant

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

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

Complement graph

compl=GraphData[{"Path",2},"ComplementGraph","Name"]

Line graph

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

LineGraphQ[GraphData[{"Path",2}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",2}&]

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

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",2},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",2}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Path", 3}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData[{"Path",3},"Configuration"]

GraphData[{"Path",3},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",3},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",3},"Polyhedron"]

Path construction

MyPathGraph[3,GraphLayout->#]&/@{"CircularEmbedding","LinearEmbedding","SpiralEmbedding","ZigZagEmbedding"}

HoneycombToroidal construction

GraphData[{"Path",3},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1]

RecognizeGraph[%]

TriangularGrid

Cases[GraphData[{"Path",3},"StandardNames"],{"TriangularHoneycombBishop",_}]

GraphData[{"Path",3},"Graph","TriangularGrid"]//StyleGraphs

GeneralizedHoneycombGraph construction

With[{n=3},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",3}}]]//Timing

g=GeneralizedHoneycombGraph[3,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",3},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",3},"Graph","IGraph"]//StyleGraphs

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Path",3}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

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

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

Complement graph

compl=GraphData[{"Path",3},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",3},"Line"]

LineGraphQ[GraphData[{"Path",3}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",3}&]

RootGraph[GraphData[{"Path",3}]]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",3},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",3}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Path", 4}

Names

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

GraphData[{"Path",4},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

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

Default embedding

GraphPlot@GraphData[{"Path",4},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData[{"Path",4},"Configuration"]

GraphData[{"Path",4},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",4},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",4},"Polyhedron"]

Path construction

MyPathGraph[4,GraphLayout->#]&/@{"CircularEmbedding","LinearEmbedding","SpiralEmbedding","ZigZagEmbedding"}//StyleGraphs

g=;

HoneycombToroidal construction

GraphData[{"Path",4},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=4},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",4}}]]//Timing

g=GeneralizedHoneycombGraph[4,2]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",4},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",4},"Graph","IGraph"]//StyleGraphs

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

Circulant

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

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

Complement graph

compl=GraphData[{"Path",4},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",4},"Line"]

LineGraphQ[GraphData[{"Path",4}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",4}&]

RootGraph[GraphData[{"Path",4}]]

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",4},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",4}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Path", 5}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",5},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",5},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData[{"Path",5},"Configuration"]

GraphData[{"Path",5},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",5},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",5},"Polyhedron"]

Path construction

MyPathGraph[5,GraphLayout->#]&/@{"CircularEmbedding","LinearEmbedding","SpiralEmbedding","ZigZagEmbedding"}//StyleGraphs

gs={,};

HoneycombToroidal construction

GraphData[{"Path",5},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=5},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",5}}]]//Timing

g=GeneralizedHoneycombGraph[5,1]

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

Circulant

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

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

Complement graph

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

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

GraphComplement/@%

Line graph

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

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

RootGraph

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",5},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",5}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Path", 6}

Names

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

GraphData[{"Path",6},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",6},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",6},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData[{"Path",6},"Configuration"]

GraphData[{"Path",6},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",6},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",6},"Polyhedron"]

Path construction

MyPathGraph[{"Path",6}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",6},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=6},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",6}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Circular

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

Planar

GraphData[{"Path",6},"Planar"]

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

MinimalCrossing

GraphData[{"Path",6},{"RCN","CN"}]

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

Circulant

GraphData[{"Path",6},"Circulant"]

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

Complement graph

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

Line graph

GraphData[{"Path",6},"Line"]

LineGraphQ[GraphData[{"Path",6}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Path",6}]]

Halin

GraphData[{"Path",6},"Halin"]

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

Rigid

GraphData[{"Path",6},"Rigid"]

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

Flexible

GraphData[{"Path",6},"Flexible"]

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

LCF

GraphData[{"Path",6},"LCF"]

GraphData[{"Path",6},"HamiltonianCycleCount"]

GraphData[{"Path",6},"LCFSignature"]

GraphData[{"Path",6},"LCFNotations"]

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

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

UnitDistance

GraphData[{"Path",6},"UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",6},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",6}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",6},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Path",6},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Path",6},"Polyhedral"]

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

{"Path", 7}

Names

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

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

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",7},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",7},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData[{"Path",7},"Configuration"]

GraphData[{"Path",7},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",7},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",7},"Polyhedron"]

Path construction

MyPathGraph[{"Path",7}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",7},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=7},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",7}}]]//Timing

g=GeneralizedHoneycombGraph[7,1]

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Circular

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

Planar

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

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

MinimalCrossing

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

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

Circulant

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

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

Complement graph

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

Line graph

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

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

RootGraph

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

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

Halin

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

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

Rigid

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

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

Flexible

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

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

LCF

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

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

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

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

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

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

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",7},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",7}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

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

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

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Path", 8}

Names

GraphData[{"Path",8},"StandardName"]

GraphData[{"Path",8},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",8},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",8},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData[{"Path",8},"Configuration"]

GraphData[{"Path",8},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",8},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",8},"Polyhedron"]

Path construction

MyPathGraph[{"Path",8}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",8},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=8},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",8}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

Bilateral

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

Circular

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

Planar

GraphData[{"Path",8},"Planar"]

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

MinimalCrossing

GraphData[{"Path",8},{"RCN","CN"}]

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

Circulant

GraphData[{"Path",8},"Circulant"]

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

Complement graph

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

Line graph

GraphData[{"Path",8},"Line"]

LineGraphQ[GraphData[{"Path",8}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Path",8}]]

Halin

GraphData[{"Path",8},"Halin"]

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

Rigid

GraphData[{"Path",8},"Rigid"]

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

Flexible

GraphData[{"Path",8},"Flexible"]

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

LCF

GraphData[{"Path",8},"LCF"]

GraphData[{"Path",8},"HamiltonianCycleCount"]

GraphData[{"Path",8},"LCFSignature"]

GraphData[{"Path",8},"LCFNotations"]

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

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

UnitDistance

GraphData[{"Path",8},"UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",8},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",8}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",8},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Path",8},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Path",8},"Polyhedral"]

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

{"Path", 9}

Names

GraphData[{"Path",9},"StandardName"]

GraphData[{"Path",9},"StandardNames"]

Primary

GraphData[{"Path",9}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",9},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",9},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",9},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",9},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",9},"Graph","Degenerate"]

Configuration

GraphData[{"Path",9},"Configuration"]

GraphData[{"Path",9},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",9},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",9},"Polyhedron"]

Path construction

MyPathGraph[{"Path",9}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",9},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=9},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",9}}]]//Timing

g=GeneralizedHoneycombGraph[9,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",9},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",9},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",9},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",9},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",9},"Planar"]

GraphData[{"Path",9},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",9},{"RCN","CN"}]

GraphData[{"Path",9},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",9},"Circulant"]

GraphData[{"Path",9},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",9},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",9},"Line"]

LineGraphQ[GraphData[{"Path",9}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",9}&]

RootGraph[GraphData[{"Path",9}]]

Halin

GraphData[{"Path",9},"Halin"]

GraphData[{"Path",9},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",9},"Rigid"]

GraphData[{"Path",9},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",9},"Flexible"]

GraphData[{"Path",9},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",9},"LCF"]

GraphData[{"Path",9},"HamiltonianCycleCount"]

GraphData[{"Path",9},"LCFSignature"]

GraphData[{"Path",9},"LCFNotations"]

GraphData[{"Path",9},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",9},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",9}],Debug->True]//Timing

GraphData[{"Path",9},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",9},"VertexList"],GraphData[{"Path",9},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",9},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",9}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",9},"Matchstick"]

GraphData[{"Path",9},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",9},"Edges"]]

3D All

GraphData[{"Path",9},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",9},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",9},"Polyhedral"]

GraphData[{"Path",9},"Graph",{"3D","Polyhedron"}]

{"Path", 10}

Names

GraphData[{"Path",10},"StandardName"]

GraphData[{"Path",10},"StandardNames"]

Primary

GraphData[{"Path",10}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",10},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",10},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",10},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",10},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",10},"Graph","Degenerate"]

Configuration

GraphData[{"Path",10},"Configuration"]

GraphData[{"Path",10},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",10},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",10},"Polyhedron"]

Path construction

MyPathGraph[{"Path",10}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",10},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=10},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",10}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",10},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",10},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",10},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",10},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",10},"Planar"]

GraphData[{"Path",10},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",10},{"RCN","CN"}]

GraphData[{"Path",10},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",10},"Circulant"]

GraphData[{"Path",10},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",10},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",10},"Line"]

LineGraphQ[GraphData[{"Path",10}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",10}&]

RootGraph[GraphData[{"Path",10}]]

Halin

GraphData[{"Path",10},"Halin"]

GraphData[{"Path",10},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",10},"Rigid"]

GraphData[{"Path",10},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",10},"Flexible"]

GraphData[{"Path",10},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",10},"LCF"]

GraphData[{"Path",10},"HamiltonianCycleCount"]

GraphData[{"Path",10},"LCFSignature"]

GraphData[{"Path",10},"LCFNotations"]

GraphData[{"Path",10},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",10},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",10}],Debug->True]//Timing

GraphData[{"Path",10},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",10},"VertexList"],GraphData[{"Path",10},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",10},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",10}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",10},"Matchstick"]

GraphData[{"Path",10},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",10},"Edges"]]

3D All

GraphData[{"Path",10},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",10},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",10},"Polyhedral"]

GraphData[{"Path",10},"Graph",{"3D","Polyhedron"}]

{"Path", 11}

Names

GraphData[{"Path",11},"StandardName"]

GraphData[{"Path",11},"StandardNames"]

Primary

GraphData[{"Path",11}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",11},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",11},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",11},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",11},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",11},"Graph","Degenerate"]

Configuration

GraphData[{"Path",11},"Configuration"]

GraphData[{"Path",11},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",11},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",11},"Polyhedron"]

Path construction

MyPathGraph[{"Path",11}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",11},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=11},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",11}}]]//Timing

g=GeneralizedHoneycombGraph[11,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",11},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",11},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",11},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",11},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",11},"Planar"]

GraphData[{"Path",11},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",11},{"RCN","CN"}]

GraphData[{"Path",11},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",11},"Circulant"]

GraphData[{"Path",11},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",11},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",11},"Line"]

LineGraphQ[GraphData[{"Path",11}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",11}&]

RootGraph[GraphData[{"Path",11}]]

Halin

GraphData[{"Path",11},"Halin"]

GraphData[{"Path",11},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",11},"Rigid"]

GraphData[{"Path",11},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",11},"Flexible"]

GraphData[{"Path",11},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",11},"LCF"]

GraphData[{"Path",11},"HamiltonianCycleCount"]

GraphData[{"Path",11},"LCFSignature"]

GraphData[{"Path",11},"LCFNotations"]

GraphData[{"Path",11},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",11},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",11}],Debug->True]//Timing

GraphData[{"Path",11},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",11},"VertexList"],GraphData[{"Path",11},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",11},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",11}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",11},"Matchstick"]

GraphData[{"Path",11},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",11},"Edges"]]

3D All

GraphData[{"Path",11},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",11},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",11},"Polyhedral"]

GraphData[{"Path",11},"Graph",{"3D","Polyhedron"}]

{"Path", 12}

Names

GraphData[{"Path",12},"StandardName"]

GraphData[{"Path",12},"StandardNames"]

Primary

GraphData[{"Path",12}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",12},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",12},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",12},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",12},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",12},"Graph","Degenerate"]

Configuration

GraphData[{"Path",12},"Configuration"]

GraphData[{"Path",12},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",12},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",12},"Polyhedron"]

Path construction

MyPathGraph[{"Path",12}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",12},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=12},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",12}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",12},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",12},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",12},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",12},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",12},"Planar"]

GraphData[{"Path",12},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",12},{"RCN","CN"}]

GraphData[{"Path",12},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",12},"Circulant"]

GraphData[{"Path",12},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",12},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",12},"Line"]

LineGraphQ[GraphData[{"Path",12}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",12}&]

RootGraph[GraphData[{"Path",12}]]

Halin

GraphData[{"Path",12},"Halin"]

GraphData[{"Path",12},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",12},"Rigid"]

GraphData[{"Path",12},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",12},"Flexible"]

GraphData[{"Path",12},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",12},"LCF"]

GraphData[{"Path",12},"HamiltonianCycleCount"]

GraphData[{"Path",12},"LCFSignature"]

GraphData[{"Path",12},"LCFNotations"]

GraphData[{"Path",12},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",12},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",12}],Debug->True]//Timing

GraphData[{"Path",12},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",12},"VertexList"],GraphData[{"Path",12},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",12},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",12}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",12},"Matchstick"]

GraphData[{"Path",12},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",12},"Edges"]]

3D All

GraphData[{"Path",12},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",12},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",12},"Polyhedral"]

GraphData[{"Path",12},"Graph",{"3D","Polyhedron"}]

{"Path", 13}

Names

GraphData[{"Path",13},"StandardName"]

GraphData[{"Path",13},"StandardNames"]

Primary

GraphData[{"Path",13}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",13},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",13},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",13},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",13},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",13},"Graph","Degenerate"]

Configuration

GraphData[{"Path",13},"Configuration"]

GraphData[{"Path",13},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",13},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",13},"Polyhedron"]

Path construction

MyPathGraph[{"Path",13}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",13},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=13},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",13}}]]//Timing

g=GeneralizedHoneycombGraph[13,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",13},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",13},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",13},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",13},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",13},"Planar"]

GraphData[{"Path",13},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",13},{"RCN","CN"}]

GraphData[{"Path",13},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",13},"Circulant"]

GraphData[{"Path",13},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",13},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",13},"Line"]

LineGraphQ[GraphData[{"Path",13}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",13}&]

RootGraph[GraphData[{"Path",13}]]

Halin

GraphData[{"Path",13},"Halin"]

GraphData[{"Path",13},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",13},"Rigid"]

GraphData[{"Path",13},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",13},"Flexible"]

GraphData[{"Path",13},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",13},"LCF"]

GraphData[{"Path",13},"HamiltonianCycleCount"]

GraphData[{"Path",13},"LCFSignature"]

GraphData[{"Path",13},"LCFNotations"]

GraphData[{"Path",13},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",13},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",13}],Debug->True]//Timing

GraphData[{"Path",13},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",13},"VertexList"],GraphData[{"Path",13},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",13},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",13}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",13},"Matchstick"]

GraphData[{"Path",13},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",13},"Edges"]]

3D All

GraphData[{"Path",13},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",13},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",13},"Polyhedral"]

GraphData[{"Path",13},"Graph",{"3D","Polyhedron"}]

{"Path", 14}

Names

GraphData[{"Path",14},"StandardName"]

GraphData[{"Path",14},"StandardNames"]

Primary

GraphData[{"Path",14}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",14},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",14},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",14},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",14},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",14},"Graph","Degenerate"]

Configuration

GraphData[{"Path",14},"Configuration"]

GraphData[{"Path",14},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",14},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",14},"Polyhedron"]

Path construction

MyPathGraph[{"Path",14}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",14},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=14},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",14}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",14},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",14},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",14},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",14},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",14},"Planar"]

GraphData[{"Path",14},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",14},{"RCN","CN"}]

GraphData[{"Path",14},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",14},"Circulant"]

GraphData[{"Path",14},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",14},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",14},"Line"]

LineGraphQ[GraphData[{"Path",14}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",14}&]

RootGraph[GraphData[{"Path",14}]]

Halin

GraphData[{"Path",14},"Halin"]

GraphData[{"Path",14},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",14},"Rigid"]

GraphData[{"Path",14},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",14},"Flexible"]

GraphData[{"Path",14},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",14},"LCF"]

GraphData[{"Path",14},"HamiltonianCycleCount"]

GraphData[{"Path",14},"LCFSignature"]

GraphData[{"Path",14},"LCFNotations"]

GraphData[{"Path",14},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",14},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",14}],Debug->True]//Timing

GraphData[{"Path",14},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",14},"VertexList"],GraphData[{"Path",14},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",14},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",14}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",14},"Matchstick"]

GraphData[{"Path",14},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",14},"Edges"]]

3D All

GraphData[{"Path",14},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",14},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",14},"Polyhedral"]

GraphData[{"Path",14},"Graph",{"3D","Polyhedron"}]

{"Path", 15}

Names

GraphData[{"Path",15},"StandardName"]

GraphData[{"Path",15},"StandardNames"]

Primary

GraphData[{"Path",15}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",15},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",15},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",15},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",15},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",15},"Graph","Degenerate"]

Configuration

GraphData[{"Path",15},"Configuration"]

GraphData[{"Path",15},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",15},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",15},"Polyhedron"]

Path construction

MyPathGraph[{"Path",15}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",15},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=15},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",15}}]]//Timing

g=GeneralizedHoneycombGraph[15,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",15},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",15},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",15},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",15},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",15},"Planar"]

GraphData[{"Path",15},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",15},{"RCN","CN"}]

GraphData[{"Path",15},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",15},"Circulant"]

GraphData[{"Path",15},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",15},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",15},"Line"]

LineGraphQ[GraphData[{"Path",15}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",15}&]

RootGraph[GraphData[{"Path",15}]]

Halin

GraphData[{"Path",15},"Halin"]

GraphData[{"Path",15},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",15},"Rigid"]

GraphData[{"Path",15},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",15},"Flexible"]

GraphData[{"Path",15},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",15},"LCF"]

GraphData[{"Path",15},"HamiltonianCycleCount"]

GraphData[{"Path",15},"LCFSignature"]

GraphData[{"Path",15},"LCFNotations"]

GraphData[{"Path",15},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",15},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",15}],Debug->True]//Timing

GraphData[{"Path",15},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",15},"VertexList"],GraphData[{"Path",15},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",15},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",15}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",15},"Matchstick"]

GraphData[{"Path",15},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",15},"Edges"]]

3D All

GraphData[{"Path",15},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",15},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",15},"Polyhedral"]

GraphData[{"Path",15},"Graph",{"3D","Polyhedron"}]

{"Path", 16}

Names

GraphData[{"Path",16},"StandardName"]

GraphData[{"Path",16},"StandardNames"]

Primary

GraphData[{"Path",16}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",16},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",16},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",16},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",16},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",16},"Graph","Degenerate"]

Configuration

GraphData[{"Path",16},"Configuration"]

GraphData[{"Path",16},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",16},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",16},"Polyhedron"]

Path construction

MyPathGraph[{"Path",16}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",16},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=16},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",16}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",16},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",16},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",16},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",16},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",16},"Planar"]

GraphData[{"Path",16},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",16},{"RCN","CN"}]

GraphData[{"Path",16},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",16},"Circulant"]

GraphData[{"Path",16},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",16},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",16},"Line"]

LineGraphQ[GraphData[{"Path",16}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",16}&]

RootGraph[GraphData[{"Path",16}]]

Halin

GraphData[{"Path",16},"Halin"]

GraphData[{"Path",16},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",16},"Rigid"]

GraphData[{"Path",16},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",16},"Flexible"]

GraphData[{"Path",16},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",16},"LCF"]

GraphData[{"Path",16},"HamiltonianCycleCount"]

GraphData[{"Path",16},"LCFSignature"]

GraphData[{"Path",16},"LCFNotations"]

GraphData[{"Path",16},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",16},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",16}],Debug->True]//Timing

GraphData[{"Path",16},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",16},"VertexList"],GraphData[{"Path",16},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",16},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",16}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",16},"Matchstick"]

GraphData[{"Path",16},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",16},"Edges"]]

3D All

GraphData[{"Path",16},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",16},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",16},"Polyhedral"]

GraphData[{"Path",16},"Graph",{"3D","Polyhedron"}]

{"Path", 17}

Names

GraphData[{"Path",17},"StandardName"]

GraphData[{"Path",17},"StandardNames"]

Primary

GraphData[{"Path",17}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",17},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",17},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",17},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",17},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",17},"Graph","Degenerate"]

Configuration

GraphData[{"Path",17},"Configuration"]

GraphData[{"Path",17},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",17},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",17},"Polyhedron"]

Path construction

MyPathGraph[{"Path",17}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",17},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=17},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",17}}]]//Timing

g=GeneralizedHoneycombGraph[17,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",17},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",17},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",17},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",17},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",17},"Planar"]

GraphData[{"Path",17},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",17},{"RCN","CN"}]

GraphData[{"Path",17},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",17},"Circulant"]

GraphData[{"Path",17},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",17},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",17},"Line"]

LineGraphQ[GraphData[{"Path",17}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",17}&]

RootGraph[GraphData[{"Path",17}]]

Halin

GraphData[{"Path",17},"Halin"]

GraphData[{"Path",17},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",17},"Rigid"]

GraphData[{"Path",17},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",17},"Flexible"]

GraphData[{"Path",17},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",17},"LCF"]

GraphData[{"Path",17},"HamiltonianCycleCount"]

GraphData[{"Path",17},"LCFSignature"]

GraphData[{"Path",17},"LCFNotations"]

GraphData[{"Path",17},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",17},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",17}],Debug->True]//Timing

GraphData[{"Path",17},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",17},"VertexList"],GraphData[{"Path",17},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",17},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",17}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",17},"Matchstick"]

GraphData[{"Path",17},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",17},"Edges"]]

3D All

GraphData[{"Path",17},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",17},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",17},"Polyhedral"]

GraphData[{"Path",17},"Graph",{"3D","Polyhedron"}]

{"Path", 18}

Names

GraphData[{"Path",18},"StandardName"]

GraphData[{"Path",18},"StandardNames"]

Primary

GraphData[{"Path",18}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",18},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",18},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",18},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",18},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",18},"Graph","Degenerate"]

Configuration

GraphData[{"Path",18},"Configuration"]

GraphData[{"Path",18},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",18},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",18},"Polyhedron"]

Path construction

MyPathGraph[{"Path",18}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",18},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=18},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",18}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",18},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",18},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",18},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",18},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",18},"Planar"]

GraphData[{"Path",18},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",18},{"RCN","CN"}]

GraphData[{"Path",18},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",18},"Circulant"]

GraphData[{"Path",18},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",18},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",18},"Line"]

LineGraphQ[GraphData[{"Path",18}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",18}&]

RootGraph[GraphData[{"Path",18}]]

Halin

GraphData[{"Path",18},"Halin"]

GraphData[{"Path",18},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",18},"Rigid"]

GraphData[{"Path",18},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",18},"Flexible"]

GraphData[{"Path",18},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",18},"LCF"]

GraphData[{"Path",18},"HamiltonianCycleCount"]

GraphData[{"Path",18},"LCFSignature"]

GraphData[{"Path",18},"LCFNotations"]

GraphData[{"Path",18},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",18},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",18}],Debug->True]//Timing

GraphData[{"Path",18},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",18},"VertexList"],GraphData[{"Path",18},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",18},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",18}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",18},"Matchstick"]

GraphData[{"Path",18},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",18},"Edges"]]

3D All

GraphData[{"Path",18},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",18},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",18},"Polyhedral"]

GraphData[{"Path",18},"Graph",{"3D","Polyhedron"}]

{"Path", 19}

Names

GraphData[{"Path",19},"StandardName"]

GraphData[{"Path",19},"StandardNames"]

Primary

GraphData[{"Path",19}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",19},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",19},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",19},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",19},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",19},"Graph","Degenerate"]

Configuration

GraphData[{"Path",19},"Configuration"]

GraphData[{"Path",19},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",19},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",19},"Polyhedron"]

Path construction

MyPathGraph[{"Path",19}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",19},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=19},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",19}}]]//Timing

g=GeneralizedHoneycombGraph[19,1]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",19},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",19},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",19},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",19},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",19},"Planar"]

GraphData[{"Path",19},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",19},{"RCN","CN"}]

GraphData[{"Path",19},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",19},"Circulant"]

GraphData[{"Path",19},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",19},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",19},"Line"]

LineGraphQ[GraphData[{"Path",19}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",19}&]

RootGraph[GraphData[{"Path",19}]]

Halin

GraphData[{"Path",19},"Halin"]

GraphData[{"Path",19},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",19},"Rigid"]

GraphData[{"Path",19},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",19},"Flexible"]

GraphData[{"Path",19},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",19},"LCF"]

GraphData[{"Path",19},"HamiltonianCycleCount"]

GraphData[{"Path",19},"LCFSignature"]

GraphData[{"Path",19},"LCFNotations"]

GraphData[{"Path",19},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",19},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",19}],Debug->True]//Timing

GraphData[{"Path",19},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",19},"VertexList"],GraphData[{"Path",19},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",19},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",19}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",19},"Matchstick"]

GraphData[{"Path",19},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",19},"Edges"]]

3D All

GraphData[{"Path",19},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",19},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",19},"Polyhedral"]

GraphData[{"Path",19},"Graph",{"3D","Polyhedron"}]

{"Path", 20}

Names

GraphData[{"Path",20},"StandardName"]

GraphData[{"Path",20},"StandardNames"]

Primary

GraphData[{"Path",20}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Path",20},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Path",20},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Path",20},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Path",20},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Path",20},"Graph","Degenerate"]

Configuration

GraphData[{"Path",20},"Configuration"]

GraphData[{"Path",20},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Path",20},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Path",20},"Polyhedron"]

Path construction

MyPathGraph[{"Path",20}[[2]],GraphLayout->#]&/@{"LinearEmbedding","CircularEmbedding","ZigZagEmbedding","SpiralEmbedding"}//StyleGraphs

gs=Rest[%]

HoneycombToroidal construction

GraphData[{"Path",20},"NotationRules","HoneycombToroidal"]

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=20},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,{"Path",20}}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"Path",20},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Path",20},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Path",20},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Path",20},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Path",20},"Planar"]

GraphData[{"Path",20},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Path",20},{"RCN","CN"}]

GraphData[{"Path",20},"Graph","MinimalCrossing"]//StyleGraphs

Circulant

GraphData[{"Path",20},"Circulant"]

GraphData[{"Path",20},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Path",20},"ComplementGraph","Name"]

Line graph

GraphData[{"Path",20},"Line"]

LineGraphQ[GraphData[{"Path",20}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"Path",20}&]

RootGraph[GraphData[{"Path",20}]]

Halin

GraphData[{"Path",20},"Halin"]

GraphData[{"Path",20},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Path",20},"Rigid"]

GraphData[{"Path",20},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Path",20},"Flexible"]

GraphData[{"Path",20},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Path",20},"LCF"]

GraphData[{"Path",20},"HamiltonianCycleCount"]

GraphData[{"Path",20},"LCFSignature"]

GraphData[{"Path",20},"LCFNotations"]

GraphData[{"Path",20},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"Path",20},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Path",20}],Debug->True]//Timing

GraphData[{"Path",20},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Path",20},"VertexList"],GraphData[{"Path",20},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"Path",20},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Path",20}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"Path",20},"Matchstick"]

GraphData[{"Path",20},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Path",20},"Edges"]]

3D All

GraphData[{"Path",20},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Path",20},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Path",20},"Polyhedral"]

GraphData[{"Path",20},"Graph",{"3D","Polyhedron"}]

GraphData

GraphDataClassString

GraphDataClassString[Select[GraphData["Path"],GraphData[#,"V"]>3&]]

GraphDataString

GraphData["Path"]

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

Do[WriteString[file,GraphDataString[
MyPathGraph[n],
"Name"->"("<>ToString[n]<>","<>ToString[n]<>")-antelope graph",
"StandardName"->{"Antelope",{n,n}},
"Classes"->{"Antelope"},
"NotationRules"->{"Antelope"->{n,n}},
"Skip"->{"Arboricity","CliqueCoveringNumber","ConnectedDominatingSets","Minors","TuttePolynomial"},
TimeConstraint->10
]],{n,16,20}]