Path Polynomial

Author

Eric W. Weisstein
February 2, 2024

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

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

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

Parametrized families

Andrasfai

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

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

FindLinearRecurrence[DeleteMissing@poly]

FindLinearRecurrence[DeleteMissing@Rest@poly]

FindPolynomialRecurrence[Drop[DeleteMissing@poly,0],3]

Antelope n×n

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

Antiprism

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

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

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

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

FindPolynomialRecurrence[Drop[DeleteMissing@poly,0],6]

FindPolynomialRecurrence[Drop[DeleteMissing@poly,0],8]

Table[FindGeneratingFunction[Drop[DeleteMissing@poly,n],x]//Head,{n,0,5}]//Union//Timing

FindGeneratingFunction[DeleteMissing@poly,x,ValidationLength->3]//Head//Timing

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

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

Apollonian

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

CoefficientList[poly,x]//Column

FindLinearRecurrence[poly]

Barbell

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

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

FindLinearRecurrence[DeleteMissing@poly]

Table[FindLinearRecurrence[Drop[DeleteMissing@poly,n]]//Head,{n,0,3}]//Union//Timing

Table[FindGeneratingFunction[Drop[DeleteMissing@poly,n],x]//Head,{n,0,3}]//Union//Timing

FindGeneratingFunction[DeleteMissing@poly,x,ValidationLength->3]//Head//Timing

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

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

Bishop n×n

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

CoefficientList[poly,x]//Column

FindLinearRecurrence[Rest@poly]

BlackBishop n×n

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

CoefficientList[DeleteMissing@poly,x]//Column

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

Camel n×n

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

CocktailParty

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

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

FindLinearRecurrence[DeleteMissing@poly]

FindLinearRecurrence[Rest@DeleteMissing@poly]

Table[FindLinearRecurrence[Drop[DeleteMissing@poly,n]]//Head,{n,0,3}]//Union//Timing

FindPolynomialRecurrence[Drop[DeleteMissing@poly,0],3]

Table[FindGeneratingFunction[Drop[DeleteMissing@poly,n],x]//Head,{n,0,3}]//Union//Timing

FindGeneratingFunction[DeleteMissing@poly,x,ValidationLength->3]//Head//Timing

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

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

Complete

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

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

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

CoefficientList[poly,x]//Column

FindLinearRecurrence[Rest@poly]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["PathPolynomial"]

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

FindLinearRecurrence[poly[[2]]]

FindLinearRecurrence[poly[[3]]]

FindLinearRecurrence[DeleteMissing@poly[[All,1]]]

FindLinearRecurrence[DeleteMissing@Drop[poly,1][[All,2]]]

FindLinearRecurrence[DeleteMissing@Drop[poly,2][[All,3]]]

CompleteBipartite n×n

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

FunctionExpand[(x^(2 n)) (((n!))^2) (BesselI[1,(2/x)]+Hypergeometric0F1Regularized[1,(1/(x^2))])-n x HypergeometricPFQ[{1},{n,1+n},(1/(x^2))]-HypergeometricPFQ[{1},{1+n,1+n},(1/(x^2))]/.n->3]

x^(2 n-1) n!^2 (BesselI[1,2/x]+Hypergeometric0F1Regularized[1,1/x^2])-n HypergeometricPFQ[{1},{n,1+n},1/x^2]-HypergeometricPFQ[{1},{1+n,1+n},1/x^2]/x/.n->3//FunctionExpand

GraphData[{"CompleteBipartite",{3,3}},"PathPolynomial"][x]

Table[(x^(2 n)) (((n!))^2) (BesselI[1,(2/x)]+Hypergeometric0F1Regularized[1,(1/(x^2))])-n x HypergeometricPFQ[{1},{n,1+n},(1/(x^2))]-HypergeometricPFQ[{1},{1+n,1+n},(1/(x^2))],{n,5}]//FunctionExpand//Expand//Column

Take[poly=DeleteMissing[Table[GraphData[{"CompleteBipartite",{n,n}},"PathPolynomial"],{n,20}]/.f_Function:>f[x]],10]//Column

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

FindLinearRecurrence[Rest@poly]

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["PathPolynomial"]

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

CoefficientList[DeleteMissing@poly,x]//Column

FindLinearRecurrence[DeleteMissing@Rest@poly]//Head

FindLinearRecurrence[DeleteMissing@poly]//Head

Table[FindLinearRecurrence[Drop[DeleteMissing@poly,n]]//Head,{n,0,3}]

FindLinearRecurrence[Drop[DeleteMissing@poly,3]]

Table[FindGeneratingFunction[Drop[DeleteMissing@poly,n],x]//Head,{n,0,3}]//Union//Timing

FindGeneratingFunction[DeleteMissing@poly,x,ValidationLength->3]//Head//Timing

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

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

Crown

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

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

FindLinearRecurrence[DeleteMissing@poly]

FindLinearRecurrence[DeleteMissing@Rest@poly]

Cycle

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

Essentially A003057

(poly=DeleteMissing[Table[GraphData[{"Cycle",n},"PathPolynomial"],{n,k0=3,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}]//Factor

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]

Empty

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

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

CoefficientList[poly,x]//Column

FindLinearRecurrence[poly]

FibonacciCube

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

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

FindLinearRecurrence[DeleteMissing@poly]//Head

FindLinearRecurrence[Rest@DeleteMissing@poly]//Head

Fiveleaper n×n

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

FoldedCube

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

CoefficientList[poly,x]//Column

Gear

Take[poly=DeleteMissing[Table[GraphData[{"Gear",n},"PathPolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x]],10]//Column

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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]

Giraffe n×n

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

Grid m×n

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

Grid n×n

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

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

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@Rest@poly]

Grid k×m×n

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

Grid n×n×n

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

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

HalvedCube

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[Rest@DeleteMissing@poly]

Hanoi

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

Helm

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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]

Hypercube

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

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

CoefficientList[poly,x]//Column

{0,0,12,24,48,72,120,96,72}/4/3

coef=Factor/@FindLinearRecurrence[Rest@poly]

Keller

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

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

King m×n

King n×n

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

coef=Factor/@FindLinearRecurrence[DeleteMissing@Rest@poly]

Knight m×n

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

Knight n×n

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

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

CoefficientList[poly,x]//Column

coef=FindLinearRecurrence[DeleteCases[poly,_Missing|0]]

FindGeneratingFunction[DeleteCases[poly,_Missing|0],x]

Ladder

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

%/. Internal`MWASymbols`Temporary`n->n//TraditionalForm

1/((-1+x^2)^3 (-1+x+x^2)^2) x^2 (-2 (-1+(-2+x) x+(x (1+x))^n)+2 x (x (-4 x+x^4-x^6-x^(2 n) (-1+x+x^2)^2 (-1-2 x+x^4))+(x (1+x))^n (-2+x^2 (4+5 x-5 x^3-4 x^4+2 x^6+x^7)))-n (-1+x) (1+x) (-1+x+x^2) (3+x (3+x (-3+x (-4+x+x^2+x^3+2 x^(2 n) (-1+x+x^2))))))/.n->3//Together//Expand

GraphData[{"Ladder",3},"PathPolynomial"][x]

(poly=Table[GraphData[{"Ladder",n},"PathPolynomial"],{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}]//Factor

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]

MengerSponge

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

MoebiusLadder

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

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

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

coef=Factor/@FindLinearRecurrence[Take[poly,19]]

Length[coef]

Take[poly,9]

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]

LinearRecurrence[{2+4 x+3 x^2,-1-8 x-12 x^2-12 x^3-x^4,-x (-4-15 x-28 x^2-20 x^3-8 x^4+5 x^5),x^2 (-6-20 x-38 x^2-28 x^3-6 x^4+8 x^5+5 x^6),x^3 (4+20 x+32 x^2+30 x^3-4 x^4-10 x^5-12 x^6+x^7),-x^4 (1+12 x+22 x^2+16 x^3-2 x^4-20 x^5-4 x^6-4 x^7+3 x^8),x^6 (3+12 x+6 x^2-4 x^3-10 x^4-8 x^5+4 x^6+x^8),-(-1+x) x^8 (1+x) (-3-4 x+x^2+2 x^4),(-1+x)^2 x^10 (1+x)^2},{3 x,6 x+12 x^2+12 x^3,9 x+18 x^2+36 x^3+36 x^4+36 x^5,12 x+24 x^2+48 x^3+80 x^4+104 x^5+112 x^6+72 x^7,15 x+30 x^2+60 x^3+100 x^4+180 x^5+230 x^6+320 x^7+220 x^8+140 x^9,18 x+36 x^2+72 x^3+120 x^4+216 x^5+348 x^6+516 x^7+708 x^8+648 x^9+468 x^10+228 x^11,21 x+42 x^2+84 x^3+140 x^4+252 x^5+406 x^6+700 x^7+1008 x^8+1540 x^9+1498 x^10+1456 x^11+784 x^12+364 x^13,24 x+48 x^2+96 x^3+160 x^4+288 x^5+464 x^6+800 x^7+1280 x^8+2000 x^9+3008 x^10+3376 x^11+3600 x^12+2512 x^13+1376 x^14+528 x^15,27 x+54 x^2+108 x^3+180 x^4+324 x^5+522 x^6+900 x^7+1440 x^8+2412 x^9+3690 x^10+5832 x^11+6912 x^12+8388 x^13+6498 x^14+4716 x^15+2088 x^16+756 x^17},{11}]//Expand

GraphData[{"MoebiusLadder",11},"PathPolynomial"][x]

Expand/@LinearRecurrence[{2+4 x+3 x^2,-1-8 x-12 x^2-12 x^3-x^4,-x (-4-15 x-28 x^2-20 x^3-8 x^4+5 x^5),x^2 (-6-20 x-38 x^2-28 x^3-6 x^4+8 x^5+5 x^6),x^3 (4+20 x+32 x^2+30 x^3-4 x^4-10 x^5-12 x^6+x^7),-x^4 (1+12 x+22 x^2+16 x^3-2 x^4-20 x^5-4 x^6-4 x^7+3 x^8),x^6 (3+12 x+6 x^2-4 x^3-10 x^4-8 x^5+4 x^6+x^8),-(-1+x) x^8 (1+x) (-3-4 x+x^2+2 x^4),(-1+x)^2 x^10 (1+x)^2},{3 x,6 x+12 x^2+12 x^3,9 x+18 x^2+36 x^3+36 x^4+36 x^5,12 x+24 x^2+48 x^3+80 x^4+104 x^5+112 x^6+72 x^7,15 x+30 x^2+60 x^3+100 x^4+180 x^5+230 x^6+320 x^7+220 x^8+140 x^9,18 x+36 x^2+72 x^3+120 x^4+216 x^5+348 x^6+516 x^7+708 x^8+648 x^9+468 x^10+228 x^11,21 x+42 x^2+84 x^3+140 x^4+252 x^5+406 x^6+700 x^7+1008 x^8+1540 x^9+1498 x^10+1456 x^11+784 x^12+364 x^13,24 x+48 x^2+96 x^3+160 x^4+288 x^5+464 x^6+800 x^7+1280 x^8+2000 x^9+3008 x^10+3376 x^11+3600 x^12+2512 x^13+1376 x^14+528 x^15,27 x+54 x^2+108 x^3+180 x^4+324 x^5+522 x^6+900 x^7+1440 x^8+2412 x^9+3690 x^10+5832 x^11+6912 x^12+8388 x^13+6498 x^14+4716 x^15+2088 x^16+756 x^17},{3,20}]

(gf=FindGeneratingFunction[Take[poly,19],x])//Head//Timing

Mycielski

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

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

Odd

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

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

Path

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

x (n-n x+x^n-1)/(x-1)^2/.n->4//Together//Expand

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

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]

PathComplement

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

CoefficientList[poly,x]//Column

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

Table[FindLinearRecurrence[Drop[DeleteMissing@poly,n]]//Head,{n,0,5}]//Union//Timing

Table[FindGeneratingFunction[Drop[DeleteMissing@poly,n],x]//Head,{n,0,5}]//Union//Timing

FindGeneratingFunction[DeleteMissing@poly,x,ValidationLength->3]//Head//Timing

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

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

Prism

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

(1/((((-1+x))^2) (((1+x))^2) (-1+2 x) (-1+x+(x^2))))n x (3 x-3 (x^2)-9 (x^3)+2 (x^4)+9 (x^5)-(x^6)-(x^7)-2 (x^8)+4 (x^(1+2 n))-6 (x^(2+2 n))+2 n (x^(2+2 n))-10 (x^(3+2 n))-6 n (x^(3+2 n))+10 (x^(4+2 n))+8 (x^(5+2 n))+10 n (x^(5+2 n))+4 (x^(6+2 n))-2 n (x^(6+2 n))-4 (x^(7+2 n))-4 n (x^(7+2 n))-4 (x^(8+2 n))-((((1-x) x))^n)+x ((((1-x) x))^n)+3 (x^2) ((((1-x) x))^n)-2 (x^3) ((((1-x) x))^n)-3 (x^4) ((((1-x) x))^n)+(x^5) ((((1-x) x))^n)+(x^6) ((((1-x) x))^n)-(((x (1+x)))^n)-x (((x (1+x)))^n)+3 (x^2) (((x (1+x)))^n)+12 (x^3) (((x (1+x)))^n)-5 (x^4) (((x (1+x)))^n)-15 (x^5) (((x (1+x)))^n)-(x^6) (((x (1+x)))^n)+4 (x^7) (((x (1+x)))^n)+4 (x^8) (((x (1+x)))^n))/.n->10//Together//Expand

Take[poly=DeleteMissing[Table[GraphData[{"Prism",n},"PathPolynomial"],{n,k0=3,kmax=25}]/.f_Function:>f[x]],10]//Column

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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]

Queen n×n

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

Rook n×n

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

RookComplement n×n

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

SierpinskiCarpet

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

SierpinskiSieve

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

SierpinskiTetrahedron

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

Star

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

1/2 (n-1) x (2+(n-2) x)/.n->1//Expand

1/2 (n-1) x (2+(n-2) x)/.n->2//Expand

1/2 (n-1) x (2+(n-2) x)/.n->5//Expand

GraphData[{"Star",5},"PathPolynomial"][x]

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

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]

Sun

GraphData[{"Sun",5}]

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

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

FindSequenceFunction[{80,255,595,970,1030,645,215,30},n]

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

Sunlet

(poly=DeleteMissing[Table[GraphData[{"Sunlet",n},"PathPolynomial"],{n,k0=3,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}]//Factor

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]

Tetrahedral

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

TorusGrid n×n

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

CoefficientList[DeleteMissing@poly,x]//Column

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

Transposition

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

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

Triangular

(poly=Table[GraphData[{"Triangular",n},"PathPolynomial"],{n,k0=2,kmax=15}]/.f_Function:>f[x])//Column

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

coef=Factor/@FindLinearRecurrence[Rest@DeleteMissing@poly]

TriangularGrid

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

Table[FindLinearRecurrence[Drop[DeleteMissing@poly,n]]//Head,{n,0,3}]

FindLinearRecurrence[Drop[DeleteMissing@poly,3]]

Table[FindGeneratingFunction[Drop[DeleteMissing@poly,n],x]//Head,{n,0,3}]//Union//Timing

FindGeneratingFunction[DeleteMissing@poly,x,ValidationLength->3]//Head//Timing

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

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

TriangularHoneycombAcuteKnight

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

CoefficientList[poly,x]//Column

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

TriangularHoneycombBishop

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

TriangularHoneycombObtuseKnight

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

TriangularHoneycombQueen

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

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@Rest@poly]

TriangularHoneycombRook

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

CoefficientList[poly,x]//Column

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

Web

Take[poly=DeleteMissing[Table[GraphData[{"Web",n},"PathPolynomial"],{n,k0=3,kmax=20}]/.f_Function:>f[x]],10]//Column

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

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

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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]

Wheel

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

((n-1) (2 x^n (1+(-1+2 n (x-1)-4 x) x^2)+x^2 (-4+x (8+6 x-2 x^3+n (x-1) (x+1)^2))))/(2 x (x-1)^3)/.n->5//Together//Expand

GraphData[{"Wheel",5},"PathPolynomial"][x]

(poly=DeleteMissing[Table[GraphData[{"Wheel",n},"PathPolynomial"],{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}]//Factor

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]

WhiteBishop n×n

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

CoefficientList[poly,x]//Column

coef=Factor/@FindLinearRecurrence[poly]

Zebra n×n

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

Algorithm

FindAllPaths

PathPolynomial[GraphData[{5,31}],x,Method->"FindAllPaths",Debug->True]

DeleteCases[Monitor[{g=#,Expand@GraphData[#,"PathPolynomial"][x],PathPolynomial[GraphData[#],x,Method->"FindAllPaths"]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

FindKPaths

PathPolynomial[GraphData[{5,31}],x,Method->"FindKPathsOnNonequivalentPairs",Debug->True]

GraphData[{5,31},"PathPolynomial"][x]

DeleteCases[Monitor[{g=#,Expand@GraphData[#,"PathPolynomial"][x],PathPolynomial[GraphData[#],x,Method->"FindPathIncrementalNonequivalentPairs"]}&/@GraphData[;;10],g],{_,x_,x_}]//Timing

PathExtension

<<MathWorld`Graphs`

VertexPairOrbits[GraphData["Q3"]]

PathPolynomialByPathExtension[g_System`Graphs,x_,opts___?OptionQ]:=Module[
{
a=AdjacencyList[g],
debug=Debug/.{opts}/.Debug->False,
pairorbits=VertexPairOrbits[g],
paths
},
paths=
]

AdjacencyList[GraphData["Q2"]]