Distance Polynomial

Author

Eric W. Weisstein
November 15, 2016

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

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

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

Compute

TextGrid[Sort[GraphData[#,{"V","#"}]&/@GraphData["DistancePolynomial","Missing"]],Dividers->All]

Special Cases

{"AlternatingGroupGraph", 7}

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"AlternatingGroupGraph",7}]]//N];//Timing

Max[e-Round[e]]

e

{"Cage", {5, 12}}

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"Cage",{5,12}}]]//N];//Timing

Max[e-Round[e]]

es=Union[Round[e 10^6]]/10^6.

InputForm[e1=Mean[Select[e,Abs[#-es[[1]]]<=10^-5&]]]

ContinuedFraction[Abs[e1]]

FromContinuedFraction[{84,{1,1,1,3,1,1,1,68}}]

InputForm[e2=Mean[Select[e,Abs[#-es[[3]]]<=10^-5&]]]

ContinuedFraction[Abs[e2]]

FromContinuedFraction[{15,2,1,{3,1,1,1,68,1,1,1}}]

t=Tally[ReplaceWithExact[e,{-(50+20 (Sqrt[3])),-(50-20 (Sqrt[3]))}]]

Expand[(x-(-50-20 (Sqrt[3])))(x-(-50+20 (Sqrt[3])))]//Factor

Factor[(((1300+100 x+(x^2)))^350)TallyToPolynomial[{{14109,1},{819,1},{42,650},{-26,728},{18,650}},x]]

{"Cage", {12, 8}}

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"Cage",{12,8}}]]//N];//Timing

Max[e-Round[e]]

es=Union[Round[e 10^6]]/10^6.

InputForm[e1=Mean[Select[e,Abs[#-es[[1]]]<=10^-5&]]]

ContinuedFraction[Abs[e1]]

t1=-FromContinuedFraction[{33,{2,1,1,1,2,18}}]

InputForm[e2=Mean[Select[e,Abs[#-es[[2]]]<=10^-5&]]]

ContinuedFraction[Abs[e2]]

t2=-FromContinuedFraction[{14,1,1,{1,1,1,2,18,2}}]

t=Tally[ReplaceWithExact[e,{t1,t2}]]

Expand[(x-t1)(x-t2)]//Factor

Factor[(((488+48 x+(x^2)))^792)TallyToPolynomial[{{9956,1},{1220,1},{20,1342}},x]]

{"Cage", {14, 8}}

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"Cage",{14,8}}]]//N];//Timing

Max[e-Round[e]]

es=Union[Round[e 10^6]]/10^6.

InputForm[e1=Mean[Select[e,Abs[#-es[[1]]]<=10^-5&]]]

ContinuedFraction[Abs[e1]]

t1=-FromContinuedFraction[{38,{5,20}}]

InputForm[e2=Mean[Select[e,Abs[#-es[[2]]]<=10^-5&]]]

ContinuedFraction[Abs[e2]]

t2=-FromContinuedFraction[{17,1,4,{20,5}}]

t=Tally[ReplaceWithExact[e,{t1,t2}]]

Expand[(x-t1)(x-t2)]//Factor

Factor[(((680+56 x+(x^2)))^1274)TallyToPolynomial[Cases[t,{_Integer,_}],x]]

{"CubeConnectedCycle", 8}

GraphDistanceMatrix[GraphData[{"CubeConnectedCycle",8}]];//Timing

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"CubeConnectedCycle",8}]]//N];//Timing

e

e=Eigenvalues[N[GraphDistanceMatrix[GraphData[{"CubeConnectedCycle",8}]],20]];//Timing

Takes > 1 hr and > 8 GB

char=CharacteristicPolynomial[GraphDistanceMatrix[GraphData[{"CubeConnectedCycle",8}]],x];//Timing

char=CharacteristicPolynomial[N[GraphDistanceMatrix[GraphData[{"CubeConnectedCycle",8}]]],x];//Timing

char

char=CharacteristicPolynomial[N[GraphDistanceMatrix[GraphData[{"CubeConnectedCycle",8}]],20],x];//Timing

char

{"Kneser", {14, 5}}

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"Kneser",{14,5}}]]//N];//Timing

Max[e-Round[e]]

c=Tally[Round[e]]

TallyToPolynomial[c,x]

{"Kneser", {14, 6}}

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"Kneser",{14,6}}]]//N];//Timing

Max[e-Round[e]]

c=Tally[Round[e]]

TallyToPolynomial[c,x]

{"MengerSponge", 3}

{"Odd", 7}

e=Eigenvalues[GraphDistanceMatrix[GraphData[{"Odd",7}]]//N];//Timing

Max[e-Round[e]]

c=Tally[Round[e]]

TallyToPolynomial[c,x]

{"SierpinskiCarpet", 4}

{"SierpinskiTetrahedron", 6}

"SuzukiGraph"

e=Eigenvalues[GraphDistanceMatrix[GraphData["SuzukiGraph"]]//N];//Timing

Max[e-Round[e]]

c=Tally[Round[e]]

TallyToPolynomial[c,x]

Families

Andrasfai

(poly=Factor@Table[GraphData[{"Andrasfai",n},"DistancePolynomial"],{n,k0=2,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Antiprism

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

(poly=Factor@Table[GraphData[{"Antiprism",n},"DistancePolynomial"],{n,k0=3,25}])//Column

CoefficientList[Take[poly,5],x]

Reverse[-{0,0,-80,-352,-524,-304,-64}]

FindLinearRecurrence[poly]//Head//Timing

(poly2=Table[((poly[[n-2]])/((x-Binomial[n+1,2])(x^(2Ceiling[n/2-1])))),{n,3,25}])//Column

FindLinearRecurrence[poly2]//Head//Timing

coef=Factor/@FindPolynomialRecurrence[poly,7]

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-1))FindGeneratingFunction[poly,z]]

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

Barbell

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

Book

(poly=Factor@Table[GraphData[{"Book",n},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

CocktailParty

(poly=Factor@Table[GraphData[{"CocktailParty",n},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

Complete

Entity["Graph",{"Complete",n}]["DistancePolynomial"]

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

CompleteBipartite m×n

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

(poly=Factor@Table[GraphData[{"CompleteBipartite",{2,n}},"DistancePolynomial"],{n,k0=3,10}])//Column

(poly=Factor@Table[GraphData[{"CompleteBipartite",{3,n}},"DistancePolynomial"],{n,k0=3,10}])//Column

(((2+x))^m)((m-2)

(((2+x))^(-2+2 n)) (2-3 n+x) (2-n+x)

(((2+x))^(-2+2 n)) (2-3 n+x) (2-n+x)

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["DistancePolynomial"]

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

(poly=Factor@Table[GraphData[{"CompleteTripartite",{n,n,n}},"DistancePolynomial"],{n,k0=2,6}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

x=.

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

CrossedPrism

(poly=Factor@Table[GraphData[{"CrossedPrism",n},"DistancePolynomial"],{n,k0=4,20,2}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Crown

(poly=Factor@Table[GraphData[{"Crown",n},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

CubeConnectedCycle

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

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

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

Cycle

Entity["Graph",{"Cycle",n}]["DistancePolynomial"]

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

Odd

poly[[;;;;2]]//Column

coef=Factor/@FindLinearRecurrence[poly[[;;;;2]]]

FindSequenceFunction[{2,6,12,20,30,42,56,72},n-1]//Factor

Table[n(n-1),{n,10}]

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

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

(odd=Table[(Sqrt[((GraphData[{"Cycle",n},"DistancePolynomial"])/((-x+(1/4) (-1+n) (1+n))))]),{n,3,20,2}]//Cancel//PowerExpand)//Column

coef=Factor/@FindLinearRecurrence[odd]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

gf=Factor[FindGeneratingFunction[odd,z]]

oddsoln=FullSimplify[SeriesCoefficient[z gf,{z,0,k}],k>0&&k∈Integers]

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

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

Solve[2k+1==n,k]

oddsoln2=oddsoln/.k->(n-1)/2//Simplify

oddsoln2=(x^k)Fibonacci[2k+1,1/Sqrt[x]]/.k->(n-1)/2//Simplify

Table[((1/4) ((n^2)-1)-x)(oddsoln2^2),{n,3,20,2}]//FullSimplify//Factor//Column

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

Table[(1/4) (1-(n^2)+4 x) (x^(n-1)) ((Fibonacci[n,(1/(Sqrt[x]))])^2),{n,3,20,2}]//Factor//Column

Even

poly[[2;;;;2]]//Column

coef=Factor/@FindLinearRecurrence[poly[[2;;;;2]]]

even=Table[((GraphData[{"Cycle",n},"DistancePolynomial"])/(((((n/2))^2)-x)(x^(n/2-1)))),{n,4,20,2}]//Cancel

coef=Factor/@FindLinearRecurrence[even]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

gf=Factor[FindGeneratingFunction[even,z]]

evensoln=FullSimplify[SeriesCoefficient[z gf,{z,0,k}],k>0&&k∈Integers]

Solve[2(k+1)==n,k]//FullSimplify

evensoln2=evensoln/.k->n/2-1//Simplify

Table[((((n/2))^2)-x)(x^(n/2-1))evensoln2,{n,4,20,2}]//FullSimplify//Factor//Column

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

CoefficientList[%,x]//Column

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

Table[(1/2)((((-1))^(n/2))(x^(n/2)) ChebyshevT[n,I/(Sqrt[x])]+(x^(n/2)))(x-(((n/2))^2))(x^(n/2-1)),{n,4,20,2}]//Factor//Column

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

Table[(1/8) (4 x-(n^2)) (x^(n-1)) ((I^n) ChebyshevT[n,(I/(Sqrt[x]))]+1),{n,4,20,2}]//Factor//Column

Both

(tabl1=Table[(((-1))^n)GraphData[{"Cycle",n},"DistancePolynomial"],{n,3,20}])//Column

(tabl2=Table[Piecewise[{
{ (4x+1-(n^2)) (x^(n-1)) ((Fibonacci[n,(1/(Sqrt[x]))])^2)/4,Mod[n,2]==1},
{(4 x-(n^2)) (x^(n-1)) ((I^n) ChebyshevT[n,(I/(Sqrt[x]))]+1)/8,Mod[n,2]==0}}],{n,3,20}]//Factor)//Column

tabl1-tabl2

Empty

Entity["Graph",{"Empty",n}]["DistancePolynomial"]

(poly=Factor@Table[GraphData[{"Empty",n},"DistancePolynomial"],{n,k0=1,kmax=30}]/.f_Function:>f[x])

FoldedCube

(poly=Factor@Table[GraphData[{"FoldedCube",n},"DistancePolynomial"],{n,k0=2,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Gear

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,8]

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-1))FindGeneratingFunction[poly,z]]

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

Grid m×n

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

Grid n×n

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

(poly=Factor@Table[GraphData[{"Grid",{n,n}},"DistancePolynomial"],{n,k0=2,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Grid k×m×n

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

Grid n×n×n

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

(poly=Factor@Table[GraphData[{"Grid",{n,n,n}},"DistancePolynomial"],{n,k0=2,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

HalvedCube

(poly=Factor@Table[GraphData[{"HalvedCube",n},"DistancePolynomial"],{n,k0=3,10}])//Column

GraphData[{"HalvedCube",1},"DistancePolynomial"]

GraphData[{"HalvedCube",2},"DistancePolynomial"]

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

FindSequenceFunction[{1,3,8,20,48,112,256},n-1]//Factor

FindSequenceFunction[{3,10,25,56,119,246,501},n-3]//Factor

(poly=Table[(x-(2^(-3+n)) n)(x^(((2^(n-1))-n-1)))((((2^(n-3))+x))^n),{n,3,20}])//Factor//Column

coef=Factor/@FindLinearRecurrence[poly]

Helm

(poly=Factor@Table[GraphData[{"Helm",n},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Hypercube

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

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

FindSequenceFunction[{12,32,80,192,448,1024,2304},n-2]

FindSequenceFunction[{4,11,26,57,120,247},n-2]

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

Keller

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

(poly=Factor@Table[GraphData[{"Keller",n},"DistancePolynomial"],{n,k0=2,5}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

King n×n

(poly=Factor@Table[GraphData[{"King",{n,n}},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Knight m×n

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

Knight n×n

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

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"DistancePolynomial"],{n,k0=4,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Ladder

Entity["Graph",{"Ladder",n}]["DistancePolynomial"]

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

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

Simpified

Table[((GraphData[{"Ladder",n},"DistancePolynomial"])/((x^(n-1))(x+n))),{n,8}]//Factor//Column

coef=Factor/@FindLinearRecurrence[rpoly=Table[((GraphData[{"Ladder",n},"DistancePolynomial"])/((x^(n-1))(x+n))),{n,20}]]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

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

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

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

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

Reverse/@CoefficientList[Table[ChebyshevU[n,2x-1],{n,0,10}],x]//Flatten

Reverse/@CoefficientList[ChebyshevU[Range[0,10],2x-1],x]//Flatten

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

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

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

FullSimplify[(1/2) (x^n)+(1/2)(((-1))^n)(x^n) ChebyshevT[2n,I/(Sqrt[x])]-(n+1)(((-x))^(n-1))ChebyshevU[n-1,-2/x-1],n∈Integers&&n>0&&x∈Reals]

FullSimplify[(((x^(1+n))+(((-x))^n) (x ChebyshevT[2 n,(I/(Sqrt[x]))]+2 (1+n) ChebyshevU[-1+n,-((2+x)/x)]))/(2 x))(x^(n-1))(x+n),n∈Integers&&n>0&&x∈Reals]

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

Attempt to simplify Chebyshev expression

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

CoefficientList[%,x]

Full expression

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]

LadderRung

(poly=Factor@Table[GraphData[{"LadderRung",n},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["DistancePolynomial"]

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

FindLinearRecurrence[poly]//Head//Timing

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

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

GraphData[{"MoebiusLadder",8},"DistanceMatrix"]//MatrixForm

Path

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

Prism

Entity["Graph",{"Prism",n}]["DistancePolynomial"]

(poly=Factor@Table[GraphData[{"Prism",n},"DistancePolynomial"],{n,k0=3,25}])//Column

CoefficientList[Take[poly,5],x]

FindLinearRecurrence[poly]//Head//Timing

Odd

FindSequenceFunction[{7,17,31,49,71},(n-1)/2]//Factor

(oddpoly=Factor@Table[(Sqrt[((GraphData[{"Prism",n},"DistancePolynomial"])/((x-(1/2) (-1+2 n+(n^2)))(x^(n-1))(n+x)))]),{n,k0=3,25,2}]//PowerExpand)//Column

CoefficientList[oddpoly,x]

A123519

Reverse/@%

Table[2^k*Binomial[n+k,2*k],{n,10},{k,0,n}]

Sum[2^k*Binomial[n+k,2*k](x^k),{k,0,n}]//FullSimplify

CoefficientList[Table[(((Sqrt[2]) Cosh[(2 n+1) ArcSinh[(Sqrt[x/2])]])/(Sqrt[2+x])),{n,0,10}]//FunctionExpand//Simplify,x]

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

Sum[2^k*Binomial[n+k,2*k](x^(n-k)),{k,0,n}]//FunctionExpand//FullSimplify

Table[(((x^n) Cosh[(1+2 n) ArcSinh[(1/((Sqrt[2]) (Sqrt[x])))]])/(Sqrt[1+(1/(2 x))])),{n,10}]//FunctionExpand//Simplify//Column

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

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

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

FunctionExpand[(((x^n) Cosh[(1+2 n) ArcSinh[(1/((Sqrt[2]) (Sqrt[x])))]])/(Sqrt[1+(1/(2 x))]))]

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

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

coef=Factor/@FindLinearRecurrence[oddpoly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

gf=Factor[z FindGeneratingFunction[oddpoly,z]]

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

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

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

Even

FindSequenceFunction[{12,24,40,60,84,112},n/2-1]//Factor

(evenpoly=Factor@Table[((GraphData[{"Prism",n},"DistancePolynomial"])/((x-(1/2) n (2+n))(n+x)(x^(3n/2-2)))),{n,k0=4,25,2}])//Column

CoefficientList[oddpoly,x]

Reverse/@%

coef=Factor/@FindLinearRecurrence[evenpoly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

gf=Factor[z FindGeneratingFunction[evenpoly,z]]

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

evenpoly//Expand//Column

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

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

CoefficientList[p1,x]

Reverse/@%

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

CoefficientList[p2,x]

Reverse/@%

Queen n×n

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

FindLinearRecurrence[poly]//Head//Timing

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

Rook n×n

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

FindLinearRecurrence[poly]//Head//Timing

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

FindPolynomialRecurrence[poly,5]

FindSequenceFunction[{12,24,40,60,84,112,144,180},n-2]//Factor

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

coef=Factor/@FindLinearRecurrence[poly]

Star

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

(poly=Factor@Table[GraphData[{"Star",n},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

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

Sun

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,8]

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-1))FindGeneratingFunction[poly,z]]

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

Sunlet

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Transposition

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

(poly=Factor@Table[GraphData[{"Transposition",n},"DistancePolynomial"],{n,k0=2,6}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["DistancePolynomial"]

MatrixForm/@Table[GraphDistanceMatrix[TrapezohedralGraph[n]],{n,3,7}]

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

FindGeneratingFunction[Take[poly,10],z]//Head//Timing

TriangularGrid

(poly=Factor@Table[GraphData[{"TriangularGrid",n},"DistancePolynomial"],{n,k0=3,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Web

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

FindLinearRecurrence[poly]//Head//Timing

coef=Factor/@FindPolynomialRecurrence[poly,6]

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-1))FindGeneratingFunction[poly,z]]

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

Wheel

Entity["Graph",{"Wheel",n}]["DistancePolynomial"]/.f_Function:>f[x]

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

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

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

(2^(2+n)) (Sqrt[4+x])

(Sqrt[x]) (4+x) (((-2-x+(Sqrt[x]) (Sqrt[4+x])))^n)-(Sqrt[x]) (4+x) (((-2-x-(Sqrt[x]) (Sqrt[4+x])))^n)

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

CoefficientList[%,x]

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

(x+2) (Sqrt[4+x]) (((-2-x-(Sqrt[x]) (Sqrt[4+x])))^n)+(x+2) (Sqrt[4+x]) (((-2-x+(Sqrt[x]) (Sqrt[4+x])))^n)

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

Join[{{1},{2,-1}},CoefficientList[Table[(-x+2)LucasL[2(n-1), Sqrt[-x]],{n,2,5}],x]]//Flatten

A129862

CoefficientList[p2,x]

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

CoefficientList[p3,x]

CoefficientList[Table[(((-1))^n)LucasL[2n,Sqrt[x]],{n,12}],x]

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

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

Re-assemble

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

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

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

FullSimplify[(1/(((4+x))^(3/2)))(2^(-1-n)) (1+x (6+x)-n (1+2 x)) ((2^(2+n)) (Sqrt[4+x])+(2^n)(Sqrt[x]) (4+x) (((-1))^(n+1))(x^(-1/2))Fibonacci[2n,(Sqrt[x])](Sqrt[x])(Sqrt[4+x])+(2^n)(x+2)(((-1))^n)LucasL[2n,Sqrt[x]](Sqrt[4+x])),n>0&&n∈Integers]

Factor[(-1+n+2 n x-x (6+x))]

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

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

(poly=Table[GraphData[{"Wheel",n},"DistancePolynomial"],{n,k0=4,kmax=10}]/.f_Function:>Expand@f[x])//Column

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

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

Final Version

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

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