Chordless Cycle Polynomial

Author

Eric W. Weisstein
March 19, 2024

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

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

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

Parametrized families

<<MathWorld`Graphs`

Andrasfai

(poly=Table[GraphData[{"Andrasfai",n},"ChordlessCyclePolynomial"],{n,k0=10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[Print[ChordlessCyclePolynomial[AndrasfaiGraph[n],x]//Timing],{n,16}]

poly={{0.001002`,0},{0.000842`,(x^5)},{0.002267`,4 (x^4)+8 (x^5)},{0.006175`,22 (x^4)+33 (x^5)},{0.014201`,70 (x^4)+98 (x^5)+2 (x^7)},{0.028248`,170 (x^4)+238 (x^5)+17 (x^7)},{0.05472`,350 (x^4)+504 (x^5)+80 (x^7)},{0.105242`,644 (x^4)+966 (x^5)+276 (x^7)},{0.195328`,1092 (x^4)+1716 (x^5)+780 (x^7)},{0.342848`,1740 (x^4)+2871 (x^5)+1914 (x^7)},{0.593334`,2640 (x^4)+4576 (x^5)+4224 (x^7)},{1.03194`,3850 (x^4)+7007 (x^5)+8580 (x^7)},{1.67453`,5434 (x^4)+10374 (x^5)+16302 (x^7)},{2.646727`,7462 (x^4)+14924 (x^5)+29315 (x^7)},{4.025844`,10010 (x^4)+20944 (x^5)+50336 (x^7)},{6.154774`,13160 (x^4)+28764 (x^5)+83096 (x^7)}}[[All,2]]

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>0]//Factor

Antiprism

Entity["Graph",{"Antiprism",n}]["ChordlessCyclePolynomial"]

Table[GraphData[{"Antiprism",n},"ChordlessCyclePolynomial"],{n,k0=3,5}]//Column

(poly=Table[GraphData[{"Antiprism",n},"ChordlessCyclePolynomial"],{n,k0=3,25}]/.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}]

soln=RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n]

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

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

Apollonian

(poly=Table[GraphData[{"Apollonian",n},"ChordlessCyclePolynomial"],{n,6}]/.f_Function:>f[x])

Barbell

(poly=Table[GraphData[{"Barbell",n},"ChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])

Bishop n×n

(poly=Table[GraphData[{"Bishop",{n,n}},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Do[Print[{gn=GraphData[{"Bishop",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

BlackBishop n×n

(poly=Table[GraphData[{"BlackBishop",{n,n}},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Do[Print[{gn=GraphData[{"BlackBishop",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

Book

(poly=Table[GraphData[{"Book",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

CocktailParty

(poly=Table[GraphData[{"CocktailParty",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

FindSequenceFunction[seq[[2;;,1,2]],n-1]//Factor

Complete

Entity["Graph",{"Complete",n}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Complete",n},"ChordlessCyclePolynomial"],{n,30}]/.f_Function:>f[x])

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["ChordlessCyclePolynomial"][x]

Table[
GraphData[{"CompleteBipartite",{m,n}},"ChordlessCyclePolynomial"],{n,20},{m,n}]/.f_Function:>f[x]//Column//TraditionalForm

(Table[Piecewise[{{{},Min[m,n]==1}},{{4,Binomial[m,2]Binomial[n,2]}}],{n,20},{m,n}]/.f_Function:>f[x])//Column//TraditionalForm

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"CompleteBipartite",{n,n}},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

Table[Piecewise[{{0,n==1}},(1/4) (((-1+n))^2) (n^2) (x^4)],{n,20}]==poly

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"CompleteTripartite",{k,m,n}},"ChordlessCyclePolynomial"],{n,5},{m,n},{k,m}]/.f_Function:>f[x])//Column

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"CompleteTripartite",{n,n,n}},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])

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

CrossedPrism

(poly=Table[GraphData[{"CrossedPrism",2n},"ChordlessCyclePolynomial"],{n,k0=3,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}]

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

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

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

Crown

(poly=Table[GraphData[{"Crown",n},"ChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

FindSequenceFunction[DeleteMissing[Rest@seq][[All,1,2]],n-3]

Table[6Binomial[n,4],{n,3,20}]

FindSequenceFunction[DeleteMissing[seq][[All,-1,2]],n-2]

Table[Binomial[n,3],{n,3,20}]

Table[Piecewise[{{{{6,1}},n==3}},{{4,6Binomial[n,4]},{6,Binomial[n,3]}}],{n,3,20}]//Column

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"CubeConnectedCycle",n},"ChordlessCyclePolynomial"],{n,k0=3,8}]/.f_Function:>f[x])//Column

Do[Print[{gn=GraphData[{"CubeConnectedCycle",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Cycle",n},"ChordlessCyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])

DiagonalIntersection

A371340

(poly=Table[GraphData[{"DiagonalIntersection",n},"ChordlessCyclePolynomial"],{n,k0=3,14}]/.f_Function:>f[x])//Column

StringReplace[ToString[#,InputForm]," "->""]&/@Take[poly,5]//Column

Exponent[DeleteMissing@poly,x]

rows=Append[Drop[#,4]&/@CoefficientList[Rest[DeleteMissing[poly]],x],poly[[7,2]][[All,2]]]

Total/@Most[rows]

seq=Flatten[rows]

StringLength[ToString[Take[seq,54]]]

BFile[seq,371340,4,"~/b371340.txt"]

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing,MaxMemoryUsed[]/10^9.}],{n,3,14}]

Dipyramid

(poly=Table[GraphData[{"Dipyramid",n},"ChordlessCyclePolynomial"],{n,k0=4,20}]/.f_Function:>f[x])//Column

coef=FindLinearRecurrence[Rest@poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

soln=RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n]

...crashes in a V12 FE...

soln={{p[n,x]->(-3*n*x^4+n^2*x^4+2*x^n)/2}}

FullSimplify[(1/2) (-3 n (x^4)+(n^2) (x^4)+2 (x^n))]

Empty

Entity["Graph",{"Empty",n}]["ChordlessCyclePolynomial"][x]

poly=Table[GraphData[{"Empty",n},"ChordlessCyclePolynomial"],{n,30}]/.f_Function:>f[x]

FibonacciCube

(poly=Table[GraphData[{"FibonacciCube",n},"ChordlessCyclePolynomial"],{n,15}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindSequenceFunction[DeleteMissing@poly,n]//Head//Timing

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

Do[Print[{gn=GraphData[{"FibonacciCube",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,15}]

FoldedCube

(poly=Table[GraphData[{"FoldedCube",n},"ChordlessCyclePolynomial"],{n,2,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[Print[{gn=GraphData[{"FoldedCube",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,2,10}]

Fiveleaper n×n

(poly=Table[GraphData[{"Fiveleaper",{n,n}},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

Do[Print[{gn=GraphData[{"Fiveleaper",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

Flower

(poly=Table[GraphData[{"Flower",n},"ChordlessCyclePolynomial"],{n,5,20}]/.f_Function:>f[x])//Column

Do[Print[{k,FindLinearRecurrence[DeleteMissing@Drop[poly,k]]//Head//Timing}],{k,0,4}]

Do[Print[{k,FindGeneratingFunction[DeleteMissing@Drop[poly,k],z,ValidationLength->2]//Head//Timing}],{k,0,4}]

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Do[
Print[{gn=GraphData[{"Flower",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,5,20}]

Gear

(poly=Table[GraphData[{"Gear",n},"ChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

gf=(z^3)FindGeneratingFunction[poly,z]

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

Goldberg

(poly=Table[GraphData[{"Goldberg",n},"ChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

Do[Print[{k,FindLinearRecurrence[DeleteMissing@Drop[poly,k]]//Head//Timing}],{k,0,4}]

Do[Print[{k,FindGeneratingFunction[DeleteMissing@Drop[poly,k],z,ValidationLength->2]//Head//Timing}],{k,0,4}]

Do[
Print[{gn=GraphData[{"Goldberg",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["ChordlessCyclePolynomial"]

Table[GraphData[{"Grid",{m,n}},"ChordlessCyclePolynomial"],{n,10},{m,n}]/.f_Function:>f[x]//Column

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Grid",{n,n}},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[Rest@DeleteMissing@poly]//Head//Timing

Do[
Print[{gn=GraphData[{"Grid",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Grid",{k,m,n}},"ChordlessCyclePolynomial"],{n,5},{m,n},{k,m}]/.f_Function:>f[x])//Column

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Grid",{n,n,n}},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[
Print[{gn=GraphData[{"Grid",{n,n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

HalvedCube

(poly=Table[GraphData[{"HalvedCube",n},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

Hanoi

(poly=Table[GraphData[{"Hanoi",n},"ChordlessCyclePolynomial"],{n,5}]/.f_Function:>f[x])//Column

Do[Print[{gn=GraphData[{"Hanoi",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,5}]

Helm

(poly=Table[GraphData[{"Helm",n},"ChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])

Hypercube

Entity["Graph",{"Hypercube",n}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Hypercube",n},"ChordlessCyclePolynomial"],{n,0,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[Print[{gn=GraphData[{"Hypercube",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Keller",n},"ChordlessCyclePolynomial"],{n,5}]/.f_Function:>f[x])//Column

Do[Print[{gn=GraphData[{"Keller",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,5}]

King m×n

King n×n

(poly=Table[GraphData[{"King",{n,n}},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[Print[{gn=GraphData[{"King",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["ChordlessCyclePolynomial"]

Table[GraphData[{"Knight",{m,n}},"ChordlessCyclePolynomial"],{n,10},{m,n}]/.f_Function:>f[x]//Column//TraditionalForm

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Knight",{n,n}},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Ladder

Entity["Graph",{"Ladder",n}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Ladder",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

LadderRung

(poly=Table[GraphData[{"LadderRung",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

MengerSponge

(poly=Table[GraphData[{"MengerSponge",n},"ChordlessCyclePolynomial"],{n,3}]/.f_Function:>f[x])//Column

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"MoebiusLadder",n},"ChordlessCyclePolynomial"],{n,k0=3,25}]/.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}]

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

soln=FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n>2]

Table[(2^(-n)) ((((x (1+(Sqrt[1+4 x]))))^n)+(((x-x (Sqrt[1+4 x])))^n)),{n,3,10}]//Expand//FullSimplify//Expand//Column

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

Table[(2^(-n)) ((((x-(Sqrt[(x^2)-4 (x^3)])))^n)+(((x+(Sqrt[(x^2)-4 (x^3)])))^n)),{n,3,10}]//FullSimplify//Expand//Column

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

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

Table[n (x^4)-(((-x))^(n/2)) (x^n) LucasL[n,(1/(Sqrt[-x]))]+(x^(3 n/2)) LucasL[n,(1/(Sqrt[x]))],{n,3,10}]//Expand//Column

Mycielski

Entity["Graph",{"Mycielski",n}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Mycielski",n},"ChordlessCyclePolynomial"],{n,8}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Odd

Entity["Graph",{"Odd",n}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Odd",n},"ChordlessCyclePolynomial"],{n,7}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Pan

(poly=Table[GraphData[{"Pan",n},"ChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])

Path

Entity["Graph",{"Path",n}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Path",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

PathComplement

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

seq[[All,1,2]]

FindSequenceFunction[%,n-5]//Factor

Prism

Entity["Graph",{"Prism",n}]["ChordlessCyclePolynomial"][x][x]

(poly=Table[GraphData[{"Prism",n},"ChordlessCyclePolynomial"],{n,k0=3,25}]/.f_Function:>f[x])//Column

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}]

soln=FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n>2]

Table[Piecewise[{{3x^4,n==3}},n (x^4)+(((-x))^(n/2)) (x^n) LucasL[n,(1/(Sqrt[-x]))]+(x^(3 n/2)) LucasL[n,(1/(Sqrt[x]))]],{n,3,10}]//Expand//Column

Queen n×n

(poly=Table[GraphData[{"Queen",{n,n}},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Do[Print[{gn=GraphData[{"Queen",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

Rook m×n

(poly=Table[GraphData[{"Rook",{m,n}},"ChordlessCyclePolynomial"],{n,10},{m,n}]/.f_Function:>f[x])//Column//TraditionalForm

Rook n×n

A291909

Same as number of cycles in (Subscript[K, n,n])

(poly=Table[GraphData[{"Rook",{n,n}},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

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

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

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

RookComplement n×n

(poly=Table[GraphData[{"RookComplement",{n,n}},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindSequenceFunction[DeleteMissing@poly,n]//Factor

Table[(1/12) (-2+n) (((-1+n))^2) (n^2) (x^4) (-15+6 n+2 (x^2)),{n,10}]//Expand//Column

SierpinskiCarpet

(poly=Table[GraphData[{"SierpinskiCarpet",n},"ChordlessCyclePolynomial"],{n,4}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

SierpinskiSieve

(poly=Table[GraphData[{"SierpinskiSieve",n},"ChordlessCyclePolynomial"],{n,5}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

SierpinskiTetrahedron

(poly=Table[GraphData[{"SierpinskiTetrahedron",n},"ChordlessCyclePolynomial"],{n,6}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]

Star

Entity["Graph",{"Star",n}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Star",n},"ChordlessCyclePolynomial"],{n,25}]/.f_Function:>f[x])

Sun

(poly=Table[GraphData[{"Sun",n},"ChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])

Sunlet

(poly=Table[GraphData[{"Sunlet",n},"ChordlessCyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])

Tetrahedral

(poly=Table[GraphData[{"Tetrahedral",n},"ChordlessCyclePolynomial"],{n,6,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]

Transposition

Entity["Graph",{"Transposition",n}]["ChordlessCyclePolynomial"]

(poly=Table[GraphData[{"Transposition",n},"ChordlessCyclePolynomial"],{n,6}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Triangular

(poly=Table[GraphData[{"Triangular",n},"ChordlessCyclePolynomial"],{n,2,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

Do[Print[{gn=GraphData[{"Triangular",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,2,20}]

TriangularGrid

(poly=Table[GraphData[{"TriangularGrid",n},"ChordlessCyclePolynomial"],{n,0,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Do[Print[{gn=GraphData[{"TriangularGrid",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,0,10}]

TriangularHoneycombAcuteKnight

(poly=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

TriangularHoneycombBishop

(poly=Table[GraphData[{"TriangularHoneycombBishop",n},"ChordlessCyclePolynomial"],{n,9}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

TriangularHoneycombObtuseKnight

(poly=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

TriangularHoneycombQueen

(poly=Table[GraphData[{"TriangularHoneycombQueen",n},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

Length@DeleteMissing@seq

Do[Print[{k,FindLinearRecurrence[Drop[DeleteMissing@poly,k]]//Head//Timing}],{k,0,3}];

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Do[Print[{gn=GraphData[{"TriangularHoneycombQueen",n},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,10}]

TriangularHoneycombRook

(poly=Table[GraphData[{"TriangularHoneycombRook",n},"ChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])

Web

(poly=Table[GraphData[{"Web",n},"ChordlessCyclePolynomial"],{n,k0=4,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}]

soln=RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n]

FullSimplify[soln,n>3]

Combiation such as

n (x^4)(((-x))^(n/2)) (x^n) LucasL[n,(1/(Sqrt[-x]))]+(x^(3 n/2)) LucasL[n,(1/(Sqrt[x]))]

(gf=Factor[(z^(k0-1))FindGeneratingFunction[poly,z]])//Head//Timing

Wheel

Entity["Graph",{"Wheel",n}]["ChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Wheel",n},"ChordlessCyclePolynomial"],{n,4,20}]/.f_Function:>f[x])

WhiteBishop n×n

(poly=Table[GraphData[{"WhiteBishop",{n,n}},"ChordlessCyclePolynomial"],{n,2,10}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Do[Print[{gn=GraphData[{"WhiteBishop",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,2,10}]

Zebra n×n

(poly=Table[GraphData[{"Zebra",{n,n}},"ChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

Do[Print[{gn=GraphData[{"Zebra",{n,n}},"#"],ChordlessCyclePolynomial[GraphData[gn],x]//Timing}],{n,20}]

Checks

DateString[]

SortBy[Select[GraphData[All],MissingQ[GraphData[#,"ChordlessCyclePolynomial"]]&],GraphData[#,"V"]&]

(bad=DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ChordlessCyclePolynomial"]/.f_Function:>f[x],
Check[TimeConstrained[ChordlessCyclePolynomial[GraphData[#],x],Infinity],Print[#];$Failed]
}&/@Select[GraphData[;;40],!MissingQ[GraphData[#,"ChordlessCyclePolynomial"]]&
],gn],
{_,x_,x_}
])//Timing

bad[[All,1]]

Cases[bad,{_,_,$Aborted}]

fix=DeleteCases[bad,{_,_Missing,_}|{_,_,$Aborted}]

(bad=DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ChordlessCyclePolynomial"]/.f_Function:>f[x],
Check[TimeConstrained[ChordlessCyclePolynomial[GraphData[#],x],Infinity],Print[#];$Failed]
}&/@Select[GraphData[41;;50],!MissingQ[GraphData[#,"ChordlessCyclePolynomial"]]&
],gn],
{_,x_,x_}
])//Timing

Cases[bad,{_,_,$Aborted}]

fix=DeleteCases[bad,{_,_Missing,_}|{_,_,$Aborted}]