Centipede Graph

Author

Eric W. Weisstein
June 19, 2023

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

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

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

Sources

Youssef and Seoud

Seoud, M.Z. and Youssef, M.A.  "On Gracefulness of Disconnected Graphs."  Unpublished work.  Jan. 2017.

http://dx.doi.org/10.13140/RG.2.2.17752.49920

Image

Graphs.m

GraphicsRow[Table[Show[CentipedeGraph[n,VertexSize->{"Scaled",.1},System`VertexStyle->Red,System`EdgeStyle->Black],PlotLabel->Style[HoldForm[n]==n,FontFamily->"Times"]],{n,5}],Dividers->All]

Combinatorica (old)

GraphicsGrid[{Table[GraphPlot[Centipede[n],Method->None,PlotLabel->Subscript[c,n]],{n,5}]},Alignment->Bottom,ImageSize->400]

Special cases

With[{cl="Centipede"},TextGrid[Sort[{cl/.GraphData[#,"NotationRules"],GraphData[#,"Name"]}&/@DeleteCases[GraphData[cl],{cl,_}]],Dividers->All]]

Properties

Acyclic

seq=Table[GraphData[{"Centipede",n},"Acyclic"],{n,10}]

AdjacencyMatrixCount

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

Table[(((2n)!)/2),{n,10}]

ArcTransitive

seq=Table[GraphData[{"Centipede",n},"ArcTransitive"],{n,10}]

ArcTransitivity

seq=Table[GraphData[{"Centipede",n},"ArcTransitivity"],{n,10}]

AutomorphismCount

seq=Table[GraphData[{"Centipede",n},"AutomorphismCount"],{n,10}]

BalabanIndex

seq=Table[GraphData[{"Centipede",n},"BalabanIndex"],{n,4}]//FullSimplify

Bandwidth

Probably 2

seq=Table[GraphData[{"Centipede",n},"Bandwidth"],{n,10}]

?Bandwidth

BridgeCount

seq=Table[GraphData[{"Centipede",n},"BridgeCount"],{n,10}]

FindSequenceFunction[seq,n]

BurningNumber

seq=Table[GraphData[{"Centipede",n},"BurningNumber"],{n,10}]

CharacteristicPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"CharacteristicPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

Chordal

seq=Table[GraphData[{"Centipede",n},"Chordal"],{n,10}]

ChordCount

seq=Table[GraphData[{"Centipede",n},"ChordCount"],{n,10}]

Chordless

seq=Table[GraphData[{"Centipede",n},"Chordless"],{n,10}]

ChordlessCycleCount

seq=Table[GraphData[{"Centipede",n},"ChordlessCycleCount"],{n,10}]

Chords

seq=Table[GraphData[{"Centipede",n},"Chords"],{n,10}]

ChromaticInvariant

seq=Table[GraphData[{"Centipede",n},"ChromaticInvariant"],{n,10}]

ChromaticNumber

seq=Table[GraphData[{"Centipede",n},"ChromaticNumber"],{n,10}]

ChromaticPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"ChromaticPolynomial"],{n,k0=1,kmax=10}]/.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]

Circumference

seq=Table[GraphData[{"Centipede",n},"Circumference"],{n,10}]

Classes

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

CliqueCount

seq=Table[GraphData[{"Centipede",n},"CliqueCount"],{n,10}]

FindSequenceFunction[seq,n]

CliqueCoveringNumber

seq=Table[GraphData[{"Centipede",n},"CliqueCoveringNumber"],{n,10}]

CliqueNumber

seq=Table[GraphData[{"Centipede",n},"CliqueNumber"],{n,10}]

CliquePolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"CliquePolynomial"],{n,k0=1,kmax=10}]/.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]

ComplementOddChordlessCycleCount

seq=Table[GraphData[{"Centipede",n},"ComplementOddChordlessCycleCount"],{n,10}]

ConnectedComponentCount

seq=Table[GraphData[{"Centipede",n},"ConnectedComponentCount"],{n,10}]

ConnectedDominatingSetCount

seq=Table[GraphData[{"Centipede",n},"ConnectedDominatingSetCount"],{n,10}]

FindSequenceFunction[seq,n]

gf=x FindGeneratingFunction[seq,x]

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

ConnectedDominationNumber

seq=Table[GraphData[{"Centipede",n},"ConnectedDominationNumber"],{n,10}]

ConnectedDominationPolynomial

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

poly2=Table[Piecewise[{{x(x+2),n==1}},(x^n)(((1+x))^n)],{n,k0,kmax}]

FullSimplify[poly2-poly]

ConnectedInducedSubgraphCount

A000247

seq=Table[GraphData[{"Centipede",n},"ConnectedInducedSubgraphCount"],{n,6}]

FindSequenceFunction[DeleteMissing[seq],n]//FullSimplify

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

ConnectedInducedSubgraphPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"CharacteristicPolynomial"],{n,k0=1,kmax=10}]/.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,6}]

FullSimplify[poly2-poly]

CrossingNumber

seq=Table[GraphData[{"Centipede",n},"CrossingNumber"],{n,10}]

CycleCount

seq=Table[GraphData[{"Centipede",n},"CycleCount"],{n,10}]

CyclePolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"CyclePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x]])

Cyclic

Table[GraphData[{"Centipede",n},"Cyclic"],{n,10}]

CyclomaticNumber

seq=Table[GraphData[{"Centipede",n},"CyclomaticNumber"],{n,10}]

DetourIndex

seq=Table[GraphData[{"Centipede",n},"DetourIndex"],{n,10}]

FindSequenceFunction[seq,n]//Factor

DetourMatrix

MatrixForm/@Table[GraphData[{"Centipede",n},"DetourMatrix"],{n,10}]

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

DetourPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"DetourPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

Diameter

seq=Table[GraphData[{"Centipede",n},"Diameter"],{n,10}]

DistanceMatrix

MatrixForm/@Table[GraphData[{"Centipede",n},"DistanceMatrix"],{n,10}]

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

DistancePolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"DistancePolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

DistinguishingNumber

seq=Table[GraphData[{"Centipede",n},"DistinguishingNumber"],{n,10}]

DomaticNumber

seq=Table[GraphData[{"Centipede",n},"DomaticNumber"],{n,10}]

DominatingSetCount

seq=Table[GraphData[{"Centipede",n},"DominatingSetCount"],{n,10}]

FindSequenceFunction[seq,n]

DominationNumber

seq=Table[GraphData[{"Centipede",n},"DominationNumber"],{n,10}]

DominationPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"DominationPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

EdgeChromaticNumber

seq=Table[GraphData[{"Centipede",n},"EdgeChromaticNumber"],{n,10}]

EdgeConnectivity

Table[GraphData[{"Centipede",n},"EdgeConnectivity"],{n,10}]

EdgeCount

seq=Table[GraphData[{"Centipede",n},"EdgeCount"],{n,10}]

FindSequenceFunction[seq,n]

EdgeCoverCount

seq=Table[GraphData[{"Centipede",n},"EdgeCoverCount"],{n,10}]

FindSequenceFunction[seq,n]

EdgeCoverNumber

seq=Table[GraphData[{"Centipede",n},"EdgeCoverNumber"],{n,10}]

EdgeCoverPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"EdgeCoverPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

EulerianCycleCount

seq=Table[GraphData[{"Centipede",n},"EulerianCycleCount"],{n,10}]

FaceCount

seq=Table[GraphData[{"Centipede",n},"FaceCount"],{n,10}]

FlowPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"FlowPolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x]])

FractionalChromaticNumber

seq=Table[GraphData[{"Centipede",n},"FractionalChromaticNumber"],{n,10}]

FractionalEdgeChromaticNumber

seq=Table[GraphData[{"Centipede",n},"FractionalEdgeChromaticNumber"],{n,10}]

Girth

seq=Table[GraphData[{"Centipede",n},"Girth"],{n,10}]

Gonality

seq=Table[GraphData[{"Centipede",n},"Gonality"],{n,10}]

HamiltonConnected

seq=Table[GraphData[{"Centipede",n},"HamiltonConnected"],{n,10}]

HamiltonDecompositionCount

seq=Table[GraphData[{"Centipede",n},"HamiltonDecompositionCount"],{n,10}]

Hamiltonian

Table[GraphData[{"Centipede",n},"Hamiltonian"],{n,10}]

HamiltonianCycleCount

seq=Table[GraphData[{"Centipede",n},"HamiltonianCycleCount"],{n,10}]

HamiltonianNumber

seq=Table[GraphData[{"Centipede",n},"HamiltonianNumber"],{n,10}]

FindSequenceFunction[seq,n]

HamiltonianPathCount

seq=Table[GraphData[{"Centipede",n},"HamiltonianPathCount"],{n,10}]

HamiltonianWalkCount

seq=Table[GraphData[{"Centipede",n},"HamiltonianWalkCount"],{n,10}]

?*HamiltonianWalk*

Length/@Table[FindHamiltonianWalk[GraphData[{"Centipede",n}],All],{n,6}]

HararyIndex

seq=Table[GraphData[{"Centipede",n},"HararyIndex"],{n,10}]

seq=Table[HararyIndex[CentipedeGraph[n]],{n,20}]

FindSequenceFunction[seq,n]//FunctionExpand//FullSimplify

Table[-1-((13 n)/2)+(1/(1+n))+4 (1+n) HarmonicNumber[n],{n,10}]

HexagonCount

seq=Table[GraphData[{"Centipede",n},"HexagonCount"],{n,10}]

IdiosyncraticPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"IdiosyncraticPolynomial"][x,y],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

IndependenceNumber

seq=Table[GraphData[{"Centipede",n},"IndependenceNumber"],{n,10}]

IndependencePolynomial

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

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

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

FullSimplify[poly2-poly]

IndependenceRatio

seq=Table[GraphData[{"Centipede",n},"IndependenceRatio"],{n,10}]

FindSequenceFunction[seq,n]

IndependentEdgeSetCount

A000129

Pell numbers

seq=Table[GraphData[{"Centipede",n},"IndependentEdgeSetCount"],{n,10}]

FindSequenceFunction[DeleteMissing[seq],n]//FullSimplify

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

Fibonacci[Range[0,20],2]

FindLinearRecurrence[seq]

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

gf=x FindGeneratingFunction[seq,x]

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

IndependentVertexSetCount

A028859

seq=Table[GraphData[{"Centipede",n},"IndependentVertexSetCount"],{n,10}]

FindSequenceFunction[DeleteMissing[seq],n]//FullSimplify

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

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

(2^(n-1) Hypergeometric2F1[1/2-n/2,-(n/2),-n,-2]/.n->n+1)//Simplify

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

FullSimplify[(2^n) Hypergeometric2F1[-(1/2)-(n/2),-(n/2),-1-n,-2]]

bug(334898): FullSimplify[2^(-1 + n) Hypergeometric2F1[1/2 - n/2, -(n/2), -n, -2]] gives incorrect result

Table[(1/6) (((1+(Sqrt[3])))^n) (3+2 (Sqrt[3])),{n,10}]//Expand

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

gf=x FindGeneratingFunction[seq,x]

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

IntersectionNumber

seq=Table[GraphData[{"Centipede",n},"IntersectionNumber"],{n,10}]

KirchhoffIndex

seq=Table[GraphData[{"Centipede",n},"KirchhoffIndex"],{n,10}]

FindSequenceFunction[seq,n]//Factor

KirchhoffSumIndex

seq=Table[GraphData[{"Centipede",n},"KirchhoffSumIndex"],{n,10}]

FindSequenceFunction[seq,n]//Factor

LaplacianMatrix

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

LaplacianPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"LaplacianPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

LeafCount

seq=Table[GraphData[{"Centipede",n},"LeafCount"],{n,10}]

LongestCycleCount

seq=Table[GraphData[{"Centipede",n},"LongestCycleCount"],{n,10}]

LovaszNumber

seq=Table[GraphData[{"Centipede",n},"LovaszNumber"],{n,10}]

MatchingGeneratingPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"MatchingGeneratingPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

MatchingNumber

seq=Table[GraphData[{"Centipede",n},"MatchingNumber"],{n,10}]

MatchingPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"MatchingPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

MaximalCliqueCount

seq=Table[GraphData[{"Centipede",n},"MaximalCliqueCount"],{n,10}]

FindSequenceFunction[seq,n]

MaximalIndependentEdgeSetCount

seq=Table[GraphData[{"Centipede",n},"MaximalIndependentEdgeSetCount"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

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

MaximalIndependentVertexSetCount

seq=Table[GraphData[{"Centipede",n},"MaximalIndependentVertexSetCount"],{n,10}]

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

MaximumCliqueCount

seq=Table[GraphData[{"Centipede",n},"MaximumCliqueCount"],{n,10}]

FindSequenceFunction[seq,n]

MaximumIndependentEdgeSetCount

seq=Table[GraphData[{"Centipede",n},"MaximumIndependentEdgeSetCount"],{n,10}]

MaximumIndependentVertexSetCount

seq=Table[GraphData[{"Centipede",n},"MaximumIndependentVertexSetCount"],{n,10}]

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

MaximumLeafNumber

seq=Table[GraphData[{"Centipede",n},"MaximumLeafNumber"],{n,10}]

MaximumVertexDegree

seq=Table[GraphData[{"Centipede",n},"MaximumVertexDegree"],{n,10}]

MeanDistance

seq=Table[GraphData[{"Centipede",n},"MeanDistance"],{n,10}]

FindSequenceFunction[seq,n]

MinimalDominatingSetCount

seq=Table[GraphData[{"Centipede",n},"MinimalDominatingSetCount"],{n,10}]

FindSequenceFunction[DeleteMissing@seq,n]

MinimalDominatingSetSignature

seq=Table[GraphData[{"Centipede",n},"MinimalDominatingSetSignature"],{n,10}]//Column

MinimalEdgeCoverCount

seq=Table[GraphData[{"Centipede",n},"MinimalEdgeCoverCount"],{n,10}]

MinimalEdgeCoverSignature

seq=Table[GraphData[{"Centipede",n},"MinimalEdgeCoverSignature"],{n,10}]//Column

MinimumCliqueCoveringCount

seq=Table[GraphData[{"Centipede",n},"MinimumCliqueCoveringCount"],{n,10}]

MinimumConnectedDominatingSetCount

seq=Table[GraphData[{"Centipede",n},"MinimumConnectedDominatingSetCount"],{n,10}]

MinimumDistinguishingLabelingCount

seq=Table[GraphData[{"Centipede",n},"MinimumDistinguishingLabelingCount"],{n,10}]

FindSequenceFunction[seq,n]

FullSimplify[FindSequenceFunction[Rest@seq,n-1],n∈Integers]

FullSimplify[(2^(1+n))(2^(-1+n))]

Table[Piecewise[{{2,n==1}},(4^n)+(2^(-1+n)) (-3+(((-1))^n))],{n,10}]

MinimumDominatingSetCount

seq=Table[GraphData[{"Centipede",n},"MinimumDominatingSetCount"],{n,10}]

FindSequenceFunction[seq,n]

MinimumEdgeCoverCount

seq=Table[GraphData[{"Centipede",n},"MinimumEdgeCoverCount"],{n,10}]

MinimumVertexDegree

seq=Table[GraphData[{"Centipede",n},"MinimumVertexDegree"],{n,10}]

MolecularTopologicalIndex

seq=Table[GraphData[{"Centipede",n},"MolecularTopologicalIndex"],{n,10}]

FindSequenceFunction[seq,n]

FindSequenceFunction[Rest@seq,n]

Nonhamiltonian

Table[GraphData[{"Centipede",n},"Nonhamiltonian"],{n,10}]

NormalizedLaplacianMatrix

MatrixForm/@Table[GraphData[{"Centipede",n},"NormalizedLaplacianMatrix"],{n,10}]

OddChordlessCycleCount

seq=Table[GraphData[{"Centipede",n},"OddChordlessCycleCount"],{n,10}]

PathCount

seq=Table[GraphData[{"Centipede",n},"PathCount"],{n,10}]

FindLinearRecurrence[seq]

FindSequenceFunction[seq,n]//Factor

PathPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"PathPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

PentagonCount

seq=Table[GraphData[{"Centipede",n},"PentagonCount"],{n,10}]

Perfect

Table[GraphData[{"Centipede",n},"Perfect"],{n,10}]

ProjectivePlaneCrossingNumber

seq=Table[GraphData[{"Centipede",n},"ProjectivePlaneCrossingNumber"],{n,10}]

Radius

seq=Table[GraphData[{"Centipede",n},"Radius"],{n,10}]

RankPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"RankPolynomial"][x,y],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

RectilinearCrossingNumber

seq=Table[GraphData[{"Centipede",n},"RectilinearCrossingNumber"],{n,10}]

ReliabilityPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"ReliabilityPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

SigmaPolynomial

A008278

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

Table[CoefficientList[x^n BellB[n,1/x],x],{n,10}]

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

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

FullSimplify[poly2-poly]

SpanningTreeCount

seq=Table[GraphData[{"Centipede",n},"SpanningTreeCount"],{n,10}]

SquareCount

seq=Table[GraphData[{"Centipede",n},"SquareCount"],{n,10}]

StabilityIndex

seq=Table[GraphData[{"Centipede",n},"StabilityIndex"],{n,10}]

FindSequenceFunction[seq,n]//FullSimplify

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

TopologicalIndex

seq=Table[GraphData[{"Centipede",n},"TopologicalIndex"],{n,10}]

FindSequenceFunction[seq,n]

ToroidalCrossingNumber

seq=Table[GraphData[{"Centipede",n},"ToroidalCrossingNumber"],{n,10}]

Traceable

Table[GraphData[{"Centipede",n},"Traceable"],{n,10}]

TriangleCount

seq=Table[GraphData[{"Centipede",n},"TriangleCount"],{n,10}]

TuttePolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"TuttePolynomial"][x,y],{n,k0=1,kmax=10}]/.f_Function:>f[x]])

Untraceable

Table[GraphData[{"Centipede",n},"Untraceable"],{n,10}]

VertexConnectivity

Table[GraphData[{"Centipede",n},"VertexConnectivity"],{n,10}]

VertexCount

seq=Table[GraphData[{"Centipede",n},"VertexCount"],{n,10}]

FindSequenceFunction[seq,n]

VertexCoverNumber

vertex cover number == vertex count - independence number

seq=Table[GraphData[{"Centipede",n},"VertexCoverNumber"],{n,10}]

VertexCoverPolynomial

(poly=Factor[Table[GraphData[{"Centipede",n},"VertexCoverPolynomial"],{n,k0=1,kmax=10}]/.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,k0,kmax}]

FullSimplify[poly2-poly]

VertexDegrees

seq=Table[GraphData[{"Centipede",n},"VertexDegrees"],{n,10}]

VertexTransitive

Table[GraphData[{"Centipede",n},"VertexTransitive"],{n,10}]

WienerIndex

seq=Table[GraphData[{"Centipede",n},"WienerIndex"],{n,10}]

FindSequenceFunction[seq,n]//Factor

WienerSumIndex

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

FindSequenceFunction[seq,n]//Factor

GraphData

GraphClassString

GraphClassString[Select[GraphData["Centipede"],GraphData[#,"V"]>2&]]

GraphDataString

Do[Print[GraphDataString[Centipede[n],
"Name"->ToString[n]<>"-centipede",
"StandardName"->{"Centipede",n},
"AlternateStandardNames"->{"Firecracker",{n,2}},
"AlternateNames"->{"("<>ToString[n]<>",2)-firecracker graph"},
"Classes"->{"Centipede"},
"NotationRules"->{"Centipede"->n},
"Information"->"Centipede",
Debug->True
]],{n,9,10}]