Path Complement Graph

Author

Eric W. Weisstein
September 3, 2022

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

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

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

Figure

Graphs.m

GraphicsGrid[Partition[Table[StyleGraphs[PathComplementGraph[n],VertexSize->If[n==1,.012,{"Scaled",.05}]],{n,10}],4],Dividers->All,ImageSize->400]

GraphData

GraphicsGrid[Partition[Table[GraphData[{"PathComplement",n},"Graph","Circular"][[1]],{n,10}],UpTo[5]],Dividers->All,ImageSize->400]//StyleGraphs[#,VertexSize->{"Scaled",.05}]&

GraphComplement

GraphicsGrid[Partition[Table[GraphComplement[PathGraph[Range[n]]],{n,12}],UpTo[4]],Dividers->All]//StyleGraphs

EdgeList

GraphicsGrid[Partition[Table[Graph[Range[n],EdgeList[GraphComplement[PathGraph[Range[n]]]]],{n,12}],UpTo[4]],Dividers->All]//StyleGraphs

Special cases

TextGrid[DeleteCases[Table[{n,RecognizeGraph[GraphComplement[PathGraph[Range[n]]]]},{n,20}],{_,{"PathComplement",_}}],Dividers->All]

Properties

Acyclic

seq=Table[GraphData[{"PathComplement",n},"Acyclic"],{n,20}]

AdjacencyMatrixCount

seq=Table[GraphData[{"PathComplement",n},"AdjacencyMatrixCount"],{n,10}]

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

Arboricity

seq=Table[GraphData[{"PathComplement",n},"Arboricity"],{n,20}]

FullSimplify[FindSequenceFunction[DeleteMissing@Drop[seq,2],n-2],n∈Integers]

Table[(1/4) (2 n-3-(((-1))^n)),{n,20}]

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

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

ArcTransitive

seq=Table[GraphData[{"PathComplement",n},"ArcTransitive"],{n,20}]

ArcTransitivity

seq=Table[GraphData[{"PathComplement",n},"ArcTransitivity"],{n,20}]

AutomorphismCount

seq=Table[GraphData[{"PathComplement",n},"AutomorphismCount"],{n,20}]

BalabanIndex

seq=Table[GraphData[{"PathComplement",n},"BalabanIndex"],{n,20}]

Bandwidth

seq=Table[GraphData[{"PathComplement",n},"Bandwidth"],{n,20}]

BridgeCount

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

BurningNumber

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

BurningNumber[GraphData[{"PathComplement",8}],Debug->True]//Timing

CharacteristicPolynomial

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@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&&n∈Integers]

Chordal

seq=Table[GraphData[{"PathComplement",n},"Chordal"],{n,20}]

ChordCount

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

Table[GraphData[{"PathComplement",n},"EdgeCount"],{n,20}]

Table[Binomial[n-1,2],{n,20}]

Chordless

seq=Table[GraphData[{"PathComplement",n},"Chordless"],{n,20}]

ChordlessCycleCount

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

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]

HighlightGraph[GraphData[{"PathComplement",5},"Graph","Labeled"],UndirectedEdge@@@Partition[#,2,1,1]]&/@GraphData[{"PathComplement",5},"ChordlessCycles"]

HighlightGraph[GraphData[{"PathComplement",6},"Graph","Labeled"],UndirectedEdge@@@Partition[#,2,1,1]]&/@GraphData[{"PathComplement",6},"ChordlessCycles"]

Chords

seq=Table[GraphData[{"PathComplement",n},"Chords"],{n,20}]

ChromaticallyUnique

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

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

ChromaticInvariant

A302978

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

Table[GraphData[{"PathComplement",n},"ChromaticPolynomial"][x],{n,15}]//Column

FactorialPower[x,4]//FunctionExpand

Plot[Evaluate[Table[GraphData[{"PathComplement",n},"ChromaticPolynomial"][x],{n,5}]],{x,-1,2},PlotLegends->Automatic]

poly2=Table[((GraphData[{"PathComplement",n},"ChromaticPolynomial"][x])/(FactorialPower[x,Ceiling[n/2]]))//FunctionExpand//Cancel,{n,15}]

Derivative[1][GraphData[{"PathComplement",3},"ChromaticPolynomial"]][1]

Derivative[1][GraphData[{"PathComplement",4},"ChromaticPolynomial"]][1]

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]//Head//Timing

FindGeneratingFunction[DeleteMissing@Drop[seq,4],x]//Head//Timing

ChromaticNumber

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

ChromaticPolynomial

(poly=Factor[DeleteMissing@Table[GraphData[{"PathComplement",n},"ChromaticPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x]//Column

Table[GraphData[{"PathComplement",n},"ChromaticPolynomial"][x],{n,15}]//Column

(poly2=Factor/@Table[((GraphData[{"PathComplement",n},"ChromaticPolynomial"][x])/(FactorialPower[x,Ceiling[n/2]]))//FunctionExpand//Cancel,{n,15}])//Column

coef=Factor/@FindLinearRecurrence[poly2]

poly[[2;;,-1]]

CoefficientList[%,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]

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

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

Circumference

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

Classes

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

CliqueCount

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

FindSequenceFunction[seq,n]//FullSimplify

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

CliqueCoveringNumber

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

CliqueNumber

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

CliquePolynomial

Some flavor of Lucas polynomials

(poly=Factor[Table[GraphData[{"PathComplement",n},"CliquePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[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]

CochromaticGraphNames

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

Select[GraphData["PathComplement"],GraphData[#,"ChromaticallyUnique"]=!=False&]

ComplementOddChordlessCycleCount

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

ConnectedComponentCount

seq=Table[GraphData[{"PathComplement",n},"ConnectedComponentCount"],{n,20}]

ConnectedDominatingSetCount

A302689

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

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

seq=Table[4+2^n-4n,{n,20}]

FindLinearRecurrence[seq]

LinearRecurrence[{4,-5,2},{2,0,0},20]

gf=x FindGeneratingFunction[seq,x]

InputForm[gf]

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

ConnectedDominationNumber

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

ConnectedDominationPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"ConnectedDominationPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

ConnectedInducedSubgraphCount

A132732

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

FindSequenceFunction[DeleteMissing[seq],n]

FindLinearRecurrence[DeleteMissing@Rest@seq]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]//Factor

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

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

Table[2+2^n-2n,{n,20}]

seq=Join[{1},Table[2(2^n-n),{n,20}]]

2(2^n-n)/.n->n-1

FindLinearRecurrence[Rest@seq]

Join[{1},LinearRecurrence[{4,-5,2},{2,4,10},20]]

ConnectedInducedSubgraphPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"ConnectedInducedSubgraphPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

CrossingNumber

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

CycleCount

A006184

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

seq={0,0,0,0,3,23,153,1077,8490,75234,742710,8084990,96192405,1241588865,17277139383,257810397243,4106342523108,69531388662932,1247182219179900,23622547999002444,471129863595453495,9868783491120925755,216617163296681315685,4971829898824570284305,119096935551493905531438,2972224576868227286710038,77153543251103295197353938};

FindLinearRecurrence[Drop[seq,4]]

FindGeneratingFunction[seq,x]

CyclePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"CyclePolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Cyclic

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

CyclomaticNumber

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

gf=x FindGeneratingFunction[seq,x]

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

DetourIndex

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

FindLinearRecurrence[DeleteMissing@Drop[seq,3]]

FindSequenceFunction[DeleteMissing@Drop[seq,3],n-3]

gf=(x^3) FindGeneratingFunction[DeleteMissing@Drop[seq,3],x]

FullSimplify[SeriesCoefficient[(((x^3) (10-3 x-13 (x^2)+8 (x^3)+4 (x^4)-3 (x^5)))/(((-1+x))^4)),{x,0,n}],n>0]

DetourMatrix

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

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

DetourPolynomial

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

coef=Factor/@FindLinearRecurrence[Drop[poly,3]]

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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Diameter

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

Dimension

seq=Table[GraphData[{"PathComplement",n},"Dimension"],{n,20}]

DistanceMatrix

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

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

DistancePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"DistancePolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

DistinguishingNumber

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

DomaticNumber

seq=Table[GraphData[{"PathComplement",n},"DomaticNumber"],{n,20}]

DominatingSetCount

A183155

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

FindLinearRecurrence[DeleteMissing@seq]

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

FindSequenceFunction[DeleteMissing@seq,n+1]

Table[1+(2^(1+n))-2 (1+n),{n,0,20}]

gf=FindGeneratingFunction[DeleteMissing@seq,x]

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

DominationNumber

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

DominationPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"DominationPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x]])//Column

CoefficientList[poly,x]

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]

EdgeChromaticNumber

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

EdgeConnectivity

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

EdgeCount

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

FindSequenceFunction[seq,n]

Binomial[n-1,2]

EdgeCoverCount

A302719

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

FindSequenceFunction[DeleteMissing@Drop[seq,3],n-3]//Head

FindLinearRecurrence[DeleteMissing@Drop[seq,3]]//Head

FindGeneratingFunction[DeleteMissing@seq,x]//Head

EdgeCoverNumber

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

EdgeCoverPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"EdgeCoverPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x]])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindLinearRecurrence[Rest@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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

EulerianCycleCount

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

FaceCount

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

FlowPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"FlowPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

FractionalChromaticNumber

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

FullSimplify[FindSequenceFunction[seq,n],n∈Integers]

FractionalEdgeChromaticNumber

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

Girth

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

Gonality

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

HamiltonConnected

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

HamiltonDecompositionCount

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

Hamiltonian

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

HamiltonianCycleCount

A242522

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

Join[{0,0},RecurrenceTable[{a[n]==n a[n-1]-(n-5)a[n-2]-(n-4)a[n-3]+(n-4)a[n-4],a[3]==a[4]==0,a[5]==1,a[6]==5},a,{n,20}]]

{0,0}~Join~RecurrenceTable[{a[n]==n a[n-1]-(n-5)a[n-2]-(n-4)a[n-3]+(n-4)a[n-4],a[3]==a[4]==0,a[5]==1,a[6]==5},a,{n,20}]

RSolve[{a[n]==n a[n-1]-(n-5)a[n-2]-(n-4)a[n-3]+(n-4)a[n-4],a[3]==a[4]==0,a[5]==1,a[6]==5},a[n],n]

HamiltonianNumber

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

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

HamiltonianPathCount

A001266

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

Series[Sum[n!*x^n*(1-x)^n/(1+x)^n,{n,20}]-x,{x,0,10}]/2

Sum[n!*x^n*(1-x)^n/(1+x)^n,{n,∞}]

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

FullSimplify[(((Exp[((1+x)/((-1+x) x))] (1+x) Gamma[0,((1+x)/((-1+x) x))])/((-1+x) x))-x-1)/(2x)]

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

RecurrenceTable[{a[n]==(n+1)a[n-1]-(n-2)a[n-2]-(n-5)a[n-3]+(n-3)a[n-4],a[0]==a[1]==1/2,a[2]==a[3]==0},a,{n,2,20}]

SeriesCoefficient[(((Exp[((1+x)/((-1+x) x))] (1+x) Gamma[0,((1+x)/((-1+x) x))])/((-1+x) x))-x-1)/(2x),{x,0,n}]

Gamma[0,((1+x)/((-1+x) x))]//FunctionExpand

SeriesCoefficient[(((Exp[((1+x)/((-1+x) x))] (1+x) (-ExpIntegralEi[-((1+x)/((-1+x) x))]+(1/2) (-Log[-(((-1+x) x)/(1+x))]+Log[-((1+x)/((-1+x) x))])-Log[((1+x)/((-1+x) x))]))/((-1+x) x))-x-1)/(2x),{x,0,n}]

Twice

A002464

Series[Sum[n!*x^n*(1-x)^n/(1+x)^n,{n,0,20}],{x,0,10}]

Sum[n!x^n(1-x)^n/(1+x)^n,{n,0,n}]//FullSimplify

Limit[(((-1))^n) Gamma[2+n] Gamma[-1-n,((1+x)/((-1+x) x))],n->∞]

seq=CoefficientList[Series[((Exp[((1+x)/((-1+x) x))] (1+x) Gamma[0,((1+x)/((-1+x) x))])/((-1+x) x)),{x,0,20}],x]

FindLinearRecurrence[Drop[seq,4]]

SeriesCoefficient[((Exp[((1+x)/((-1+x) x))] (1+x) Gamma[0,((1+x)/((-1+x) x))])/((-1+x) x)),{x,0,n}]

RecurrenceTable[{a[n]==(n+1)a[n-1]-(n-2)a[n-2]-(n-5)a[n-3]+(n-3)a[n-4],a[0]==a[1]==1,a[2]==a[3]==0},a,{n,0,20}]

RSolve[{a[n]==(n+1)a[n-1]-(n-2)a[n-2]-(n-5)a[n-3]+(n-3)a[n-4],a[0]==a[1]==1,a[2]==a[3]==0},a[n],n]

HamiltonianWalkCount

Maybe A153398?

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

Table[Sum_{k=0..n} C(3k+1,k)/(3k+1)*C(4n-2k,n-k)*k/(2n-k)

HararyIndex

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

gf=x FindGeneratingFunction[seq,x]

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

HexagonCount

A302695

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

coef=FindLinearRecurrence[Drop[seq,4]]

LinearRecurrence[{7,-21,35,-35,21,-7,1},{5,50,265,996,2985,7610,17185},{0,20}]

Take[Drop[seq,4],Length@coef]

Join[{0,0,0,0},LinearRecurrence[{7,-21,35,-35,21,-7,1},{0,5,50,265,996,2985,7610},20]]

FindGeneratingFunction[seq,x]

InputForm[((x(-5-15 x-20 (x^2)-16 (x^3)-3 (x^4)-(x^5)))/(((-1+x))^7))]

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

FullSimplify[SeriesCoefficient[((x(-5-15 x-20 (x^2)-16 (x^3)-3 (x^4)-(x^5)))/(((-1+x))^7)),{x,0,n}],n>0]//Factor

Table[n (4+22 n+17 (n^2)+13 (n^3)+3 (n^4)+(n^5))/12,{n,0,50}]

IdiosyncraticPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"IdiosyncraticPolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x,y]])//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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

IndependenceNumber

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

IndependencePolynomial

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

IndependenceRatio

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

FindSequenceFunction[Rest@seq,n-1]

IndependentEdgeSetCount

A170941

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

FindLinearRecurrence[DeleteMissing@seq]

FindSequenceFunction[seq,n]

seq=RecurrenceTable[{a[n+1]==a[n]+n a[n-1]-a[n-2]+a[n-3],a[0]==a[1]==a[2]==1,a[3]==2},a,{n,30}]

RSolve[{a[n+1]==a[n]+n a[n-1]-a[n-2]+a[n-3],a[0]==a[1]==a[2]==1,a[3]==2},a[n],n]

gf=FindGeneratingFunction[seq,x]//Head//Timing

IndependentVertexSetCount

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

FindSequenceFunction[seq,n]

IntersectionNumber

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

IrredundancePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"IrredundancePolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

IrredundantSetCount

A000096

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

FindSequenceFunction[DeleteMissing@seq,n]

gf=x FindGeneratingFunction[DeleteMissing@seq,x]

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

KirchhoffIndex

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

FindSequenceFunction[Drop[seq,4],n-4]//Head//Timing

FindGeneratingFunction[Drop[seq,3],x]

KirchhoffSumIndex

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

FindSequenceFunction[Drop[seq,4],n-4]//Head//Timing

LaplacianMatrix

MatrixForm/@Table[GraphData[{"PathComplement",n},"LaplacianMatrix"],{n,5}]

LaplacianPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"LaplacianPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

LeafCount

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

Likelihood

seq=Table[GraphData[{"PathComplement",n},"Likelihood"],{n,20}]

seq={1,(1/2),(1/3),(1/9),(29/1080),(2/405),(2509/3402000),(1889/20412000),(72151/7201353600),(30911/32406091200)};

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

LongestCycleCount

=== HamiltonianCycleCount

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

LongestPathCount

=== HamiltonianPathCount

seq=Table[GraphData[{"PathComplement",n},"LongestPathCount"],{n,20}]

LongestPathLength

seq=Table[GraphData[{"PathComplement",n},"LongestPathLength"],{n,20}]

LovaszNumber

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

MatchingGeneratingPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"MatchingGeneratingPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x]])//Column

CoefficientList[poly,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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MatchingNumber

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

MatchingPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"MatchingPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x]])//Column

CoefficientList[poly,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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

MaximalCliqueCount

Padovan numbers

A000931

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

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

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

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

MaximalIndependentEdgeSetCount

A302749

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

Odd

Sum_{k=0..floor(n/2)} (-1)^k*binomial(n-k,k)*(2*(ceiling(n/2)-k)-1)!!

Table[Sum[(-1)^k Binomial[n-k,k](2*(Ceiling[n/2]-k)-1)!!,{k,0,Floor[n/2]}],{n,1,10,2}]

Table[(((2^(-Floor[n/2])) n!Hypergeometric1F1[-Floor[n/2],-n,-2])/(Floor[n/2]!)),{n,20}]

Even

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

Sum[(1-k)(-1)^k Binomial[2n-k,k](2(n-k)-1)!!,{k,0,n}]

Table[%,{n,10}]

expr1=(((2^(-n)) (2 Gamma[2 n] Gamma[1+n] Hypergeometric1F1[1-n,1-2 n,-2]+Gamma[n] Gamma[1+2 n] Hypergeometric1F1[-n,-2 n,-2]))/(Gamma[n] Gamma[1+n]));

expr2=FullSimplify[expr1,n∈Integers]

Table[expr1/expr2,{n,10}]

Table[(((2^n) Gamma[(1/2)+n] (Hypergeometric1F1[1-n,1-2 n,-2]+Hypergeometric1F1[-n,-2 n,-2]))/(Sqrt[π])),{n,10}]

Table[(((2^n) Gamma[(1/2)+n] (Hypergeometric1F1[1-n,1-2 n,-2]+Hypergeometric1F1[-n,-2 n,-2]))/(Sqrt[π]))(((-1))^n),{n,10}]

FullSimplify[(((2^n) Gamma[(1/2)+n] (Hypergeometric1F1[1-n,1-2 n,-2]+Hypergeometric1F1[-n,-2 n,-2]))/(Sqrt[π]))(((-1))^n)]

Table[(((2^n) ((Sqrt[π])/(2^n))(2n-1)!! (Hypergeometric1F1[1-n,1-2 n,-2]+Hypergeometric1F1[-n,-2 n,-2]))/(Sqrt[π])),{n,10}]

FullSimplify[(((2^n) ((Sqrt[π])/(2^n))(2n-1)!! (Hypergeometric1F1[1-n,1-2 n,-2]+Hypergeometric1F1[-n,-2 n,-2]))/(Sqrt[π])),n∈Integers]

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

Both

Table[Piecewise[{{(((2^(-Floor[n/2])) n!Hypergeometric1F1[-Floor[n/2],-n,-2])/(Floor[n/2]!)),Mod[n,2]==1},{(n-1)!! (Hypergeometric1F1[1-n/2,1-n,-2]+Hypergeometric1F1[-n/2,-n,-2]),Mod[n,2]==0}}],{n,20}]

Table[If[Mod[n,2]==0,(n-1)!! (Hypergeometric1F1[1-n/2,1-n,-2]+Hypergeometric1F1[-n/2,-n,-2]),(((2^(-Floor[n/2])) n!Hypergeometric1F1[-Floor[n/2],-n,-2])/(Floor[n/2]!))],{n,20}]

MaximalIndependentVertexSetCount

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

MaximalIrredundantSetCount

A034856

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

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]//Factor

MaximalIrredundantSetSignature

seq=Table[GraphData[{"PathComplement",n},"MaximalIrredundantSetSignature"],{n,20}]

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

MaximumCliqueCount

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

FindSequenceFunction[seq,n]//FullSimplify

MaximumIndependentEdgeSetCount

A302750

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

Table[Sum[(-1)^k Binomial[n-k,k](2(Ceiling[n/2]-k)-1)!!,{k,0,Floor[n/2]}],{n,20}]

seq=Table[Sum[(-1)^k Binomial[n-k,k](2(Ceiling[n/2]-k)-1)!!,{k,0,Floor[n/2]}],{n,3,50}]

Sum[(-1)^k Binomial[n-k,k](2(Ceiling[n/2]-k)-1)!!,{k,0,Floor[n/2]}]

bug(350507): Sum[(-1)^k Binomial[n - k, k] (2 (Ceiling[n/2] - k) - 1)!!, {k, 0, Floor[n/2]}] gives incorrect result

Table[%,{n,20}]

Table[Sum[(-1)^k Binomial[n-k,k](2(Ceiling[n/2]-k)-1)!!,{k,0,n/2}],{n,20}]

Sum[(-1)^k Binomial[n-k,k](2(Ceiling[n/2]-k)-1)!!,{k,0,n/2}]

Table[(((2^(-n/2)) Gamma[1+n] Hypergeometric1F1[-(n/2),-n,-2])/(Gamma[((2+n)/2)])),{n,2,20,2}]

Sum[(-1)^k Binomial[n-k,k](2(Ceiling[n/2]-k)-1)!!,{k,0,(n-1)/2}]

Table[(((2^((1/2)-(n/2))) Gamma[1+n] Hypergeometric1F1[(1/2)-(n/2),-n,-2])/(Gamma[((1+n)/2)])),{n,1,20,2}]

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

Join[{1,1},Table[(((2^(-Floor[n/2])) n!Hypergeometric1F1[-Floor[n/2],-n,-2])/(Floor[n/2]!)),{n,3,20}]]

MaximumIndependentVertexSetCount

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

MaximumIrredundantSetCount

seq=Table[GraphData[{"PathComplement",n},"MaximumIrredundantSetCount"],{n,20}]

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]//Factor

MaximumLeafNumber

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

MaximumVertexDegree

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

MeanDistance

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

FindSequenceFunction[Drop[seq,4],n-4]//Factor

MinimalDominatingSetCount

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

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]//Factor

MinimalDominatingSetSignature

seq=Table[GraphData[{"PathComplement",n},"MinimalDominatingSetSignature"],{n,20}]

Table[{{2,(1/2) (4-3 n+(n^2))}},{n,4,20}]

MinimalEdgeCoverCount

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

MinimalEdgeCoverSignature

seq=Table[GraphData[{"PathComplement",n},"MinimalEdgeCoverSignature"],{n,20}]

MinimalTotalDominatingSetCount

seq=Table[GraphData[{"PathComplement",n},"MinimalTotalDominatingSetCount"],{n,20}]

FindSequenceFunction[DeleteMissing@Rest@seq,n-1]

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

MinimumCliqueCoveringCount

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

MinimumConnectedDominatingSetCount

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

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]//Factor

MinimumDistinguishingLabelingCount

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

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]

MinimumDominatingSetCount

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

FindSequenceFunction[Drop[seq,4],n-4]//Factor

MinimumEdgeCoverCount

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

MinimumTotalDominatingSetCount

seq=Table[GraphData[{"PathComplement",n},"MinimumTotalDominatingSetCount"],{n,20}]

FindSequenceFunction[Drop[seq,1],n-1]

MinimumVertexDegree

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

MolecularTopologicalIndex

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

FindSequenceFunction[Drop[seq,4],n-4]//Factor

Nonhamiltonian

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

Position[%,True]//Flatten

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"PathComplement",n},"NormalizedLaplacianMatrix"],{n,5}]

OddChordlessCycleCount

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

PathCount

A302734

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

FindLinearRecurrence[DeleteMissing@Drop[seq,2]]//Head//Timing

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-4]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

PathPolynomial

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindLinearRecurrence[Rest@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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

PentagonCount

A060446

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

FindLinearRecurrence[Drop[seq,3]]

seq=LinearRecurrence[{6,-15,20,-15,6,-1},{1,8,39,136,377,888},{0,20}]

FindSequenceFunction[Rest@seq,n]//Factor

Table[n(n^2+1)(n^2+4)/10,{n,0,20}]

FindGeneratingFunction[seq,x]

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

Perfect

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

Polyhedron

seq=Table[GraphData[{"PathComplement",n},"Polyhedron"],{n,20}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"PathComplement",6},"Polyhedron"]}]

ProjectivePlaneCrossingNumber

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

Radius

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

RankPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"RankPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x,y]])//Column

RectilinearCrossingNumber

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

ReliabilityPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"ReliabilityPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x]])//Column

SigmaPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"SigmaPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

Skewness

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

FindSequenceFunction[Take[seq,7],n]

FindGeneratingFunction[Take[seq,7],x]

SpanningTreeCount

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

FindSequenceFunction[DeleteMissing@Drop[seq,3],n-3]//Head//Timing

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

SpectralRadius

seq=Table[GraphData[{"PathComplement",n},"SpectralRadius"],{n,20}]

SquareCount

A002817

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

coef=FindLinearRecurrence[Drop[seq,2]]

Take[Drop[seq,2],Length@coef]

StabilityIndex

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

FindSequenceFunction[Drop[seq,4],n-4]//Head//Timing

FindLinearRecurrence[Drop[seq,4]]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

TopologicalIndex

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

FullSimplify[FindSequenceFunction[Drop[seq,4],n-4],n∈Integers]

ToroidalCrossingNumber

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

TotalDominatingSetCount

A302689

seq=Table[GraphData[{"PathComplement",n},"TotalDominatingSetCount"],{n,20}]

FindLinearRecurrence[Drop[seq,3]]

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

TotalDominationNumber

seq=Table[GraphData[{"PathComplement",n},"TotalDominationNumber"],{n,20}]

TotalDominationPolynomial

(poly=Table[GraphData[{"PathComplement",n},"TotalDominationPolynomial"]/.f_Function:>Factor@f[x],{n,20}])//Column

FindLinearRecurrence[Drop[poly,3]]

Traceable

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

Triameter

seq=Table[GraphData[{"PathComplement",n},"Triameter"],{n,20}]

TriangleCount

A000292

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

FindSequenceFunction[Drop[seq,2],n-2]//Factor

Table[(1/6) (-4+n) (-3+n) (-2+n),{n,2,20}]

Table[n*(n+1)*(n+2)/6,{n,20}]

TuttePolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"TuttePolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[x,y]])//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]

Factor[Take[poly2-poly,kmax-k0-Count[poly,_Missing]+1]]

FullSimplify[poly2-poly]

Untraceable

seq=Table[GraphData[{"PathComplement",n},"Untraceable"],{n,20}]

Position[seq,True]//Flatten

VertexConnectivity

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

VertexCount

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

FindSequenceFunction[seq,n]

VertexCoverNumber

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

VertexCoverPolynomial

(poly=DeleteMissing@Factor[Table[GraphData[{"PathComplement",n},"VertexCoverPolynomial"],{n,k0=4,kmax=20}]/.f_Function:>f[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]

VertexDegrees

seq=Table[GraphData[{"PathComplement",n},"VertexDegrees"],{n,6}]

VertexTransitive

Table[GraphData[{"PathComplement",n},"VertexTransitive"],{n,20}]

WienerIndex

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

FindSequenceFunction[Drop[seq,4],n-4]//Factor

WienerSumIndex

seq=Table[GraphData[{"PathComplement",n},"WienerSumIndex"],{n,10}]

FindSequenceFunction[Drop[seq,4],n-4]

Embeddings

{"PathComplement", 6}

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

Primary

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

All

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

Planar

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

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

MinimalCrossing

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

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

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"PathComplement",6}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"PathComplement",6}]]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[GraphData[{"PathComplement",6}],"OuterFace"->#]&/@faces

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{,}

Tutte embedding construction 4

GraphPlot[RotateGraph[,Pi/2]]

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

RecognizeGraph[g]

Tutte embedding construction 3 #1

GraphPlot[RotateGraph[]]

GraphPlot@RotateGraph[GraphicsToGraph@,2Pi/3]

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

RecognizeGraph[g]

Tutte embedding construction 3 #2

GraphPlot[RotateGraph[]]

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

RecognizeGraph[g]

Halin

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

LCF

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

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

UnitDistance

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

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

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

Matchstick

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

Default embedding

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

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

RecognizeGraph[g]

3D default

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

3D All

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

3D UnitDistance

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

3D Polyhedron

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"PathComplement",6},"Polyhedron"]}]

3D Canonical

GraphData[{"PathComplement",6},"Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData[{"PathComplement",6},"Polyhedron"],Yellow,Sphere[]}]

3D Canonical construction

Graphics3D[{FaceForm[Green,Red],poly=GraphPolyhedron[GraphData[{"PathComplement",6}],-1]}]

(can=FindCanonicalPolyhedron[poly,WorkingPrecision->100,MaxIterations->50000,PrecisionGoal->20,"ProgressInterval"->500,"TangentFactor"->1/10,"PlanarFactor"->1/10,Debug->True])//Timing

SimplePolyhedronQ[can]

Graphics3D[{Opacity[.5],Red,can,Yellow,Sphere[]}]

(lens=Mean/@Split[Sort[PolyhedronEdgeLengths[can]],Abs[#1-#2]<1.*^-10&])//N

v=PolyhedronCoordinates[can];

colors=With[{n=Length[lens]},Table[Hue[i/n],{i,0,n-1}]]

Graphics3D[{Thick,Sequence@@Nearest[Thread[lens->colors],EuclideanDistance@@v[[#]]],Line[v[[#]]]}&/@PolyhedronEdges[can],Boxed->False]

g=PolyhedronGraph[can]

GraphData

GraphDataString

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

Do[WriteString[file,GraphDataString[System`GraphComplement[PathGraph[Range[n]]],
"StandardName"->{"PathComplement",n},
"Name"->ToString[n]<>"\[Hyphen]path complement graph",
"Classes"->{"Nongrid","PathComplement"},
"NotationRules"->{"PathComplement"->n},
"Information"->"PathComplement",
(*
"Skip"->{"ChordlessCycles","Chords","ChromaticPolynomial","EdgeChromaticNumber","HamiltonianWalks","TuttePolynomial"},
*)
TimeConstraint->60,
Debug->True]],{n,{8}}]

Close[file]