Edge Cover Polynomial

Author

Eric W. Weisstein
May 26, 2024

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

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

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

Multiplicative

Select[GraphData["Disconnected"],ListQ[c=GraphData[#,"ConnectedComponentGraphNames"]]&&Quiet[FreeQ[GraphData[#,"EdgeCoverPolynomial"]&/@c,GraphData|Missing]]&&Head[GraphData[#,"EdgeCoverPolynomial"]]===Missing&]

Check

Monitor[Select[GraphData[;;7],Expand[EdgeCoverPolynomial[GraphData[g=#],x]-GraphData[#,"EdgeCoverPolynomial"]]≠0&],g]//Timing

Parametrized families

Andrasfai

(poly=Factor@Table[GraphData[{"Andrasfai",n},"EdgeCoverPolynomial"][x],{n,k0=1,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]]

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

Antiprism

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

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

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

coef=Factor/@FindPolynomialRecurrence[DeleteMissing@poly,3]

coef=Factor/@FindPolynomialRecurrence[DeleteMissing@poly,4]

coef=Factor/@FindPolynomialRecurrence[DeleteMissing@poly,5]

coef=Factor/@FindPolynomialRecurrence[DeleteMissing@poly,6]

ToPolynomialRecurrence[p,x,n,coef]

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

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]

Select[GraphData["XXX"],Expand[GraphData[#,"DominationPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Barbell

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["XXX"],Expand[GraphData[#,"DominationPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Book

(poly=Factor@Table[GraphData[{"Book",n},"EdgeCoverPolynomial"][x],{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^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["Book"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Book"/.GraphData[#,"NotationRules"]},(x^n)-2 (((x (1+x)))^n)+(1+x) (((x (1+x (3+x))))^n)]]=!=0&]

CocktailParty

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["XXX"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Complete

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

InputForm[%]

Inactivate[%[x]]

(poly=Select[Table[GraphData[{"Complete",n},"EdgeCoverPolynomial"][x],{n,n0=1,20}],FreeQ[#,Missing|GraphData]&]//Quiet)//Take[#,7]&//Column

FindLinearRecurrence

coef=Factor/@FindLinearRecurrence[poly]

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

coef=Factor/@FindLinearRecurrence[poly]

Generating Function

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

Sum

Factor/@Table[Sum[(((-1))^(n-k))Binomial[n,k](((x+1))^(Binomial[k,2])),{k,0,n}],{n,5}]//Column

bug(322281)

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

CompleteBipartite m×n

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

Sum

Factor/@Table[Sum[(((-1))^k)Binomial[m,k]((((((x+1))^(m-k))-1))^n),{k,0,m}],{n,5},{m,n}]

Table[GraphData[{"CompleteBipartite",{m,n}},"EdgeCoverPolynomial"][x],{n,5},{m,n}]

CompleteBipartite n×n

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

CompleteTripartite n×n×n

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

CrossedPrism

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["XXX"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Crown

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["XXX"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

CubeConnectedCycle

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

Cycle

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

Table[(x^(n/2)) LucasL[n,(Sqrt[x])],{n,3,20}]//Factor//Column

(poly=Select[Table[GraphData[{"Cycle",n},"EdgeCoverPolynomial"][x],{n,n0=3,20}],FreeQ[#,Missing|GraphData]&]//Quiet)//Column

FindLinearRecurrence

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

Factor/@LinearRecurrence[coef,Take[poly,Length[coef]],10]//Column

Factor/@LinearRecurrence[coef,{x,x(2+x)},10]//Column

Generating Function

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

Factor/@Series[%,{z,0,5}]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0&&n∈Integers&&x∈Reals]

RSolve

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

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

Sum

Factor/@Table[x^n+Sum[(n/(n-k))Binomial[k-1,n-k-1](x^k),{k,n-1}],{n,10}]//Column

bug(322281)

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

Subtract@@@Table[{(2^(-n)) ((((x-(Sqrt[x]) (Sqrt[4+x])))^n)+(((x+(Sqrt[x]) (Sqrt[4+x])))^n)),x^n+Sum[(n/(n-k))Binomial[k-1,n-k-1](x^k),{k,n-1}]},{n,10}]//FullSimplify//Union

DoubleCone

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

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

Empty

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

(poly=Select[Table[GraphData[{"Empty",n},"EdgeCoverPolynomial"][x],{n,n0=1,20}],FreeQ[#,Missing|GraphData]&]//Quiet)

FibonacciCube

(poly=Factor@Table[GraphData[{"FibonacciCube",n},"EdgeCoverPolynomial"],{n,k0=1,15}]/.f_Function:>f[x])//Column

FoldedCube

(poly=Factor@Table[GraphData[{"FoldedCube",n},"EdgeCoverPolynomial"][x],{n,k0=2,4}])//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^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["XXX"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Gear

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,4]

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

Select[GraphData["Gear"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Gear"/.GraphData[#,"NotationRules"]},(2^(-n)) (-(((x (2+x-(Sqrt[x]) (Sqrt[4+x]))))^n)-(((x (2+x+(Sqrt[x]) (Sqrt[4+x]))))^n)+(((x (2+3 x+(x^2)-(Sqrt[x]) (Sqrt[(1+x) (8+x (5+x))]))))^n)+(((x (2+3 x+(x^2)+(Sqrt[x]) (Sqrt[(1+x) (8+x (5+x))]))))^n))]]=!=0&]

Grid n×n

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

Grid n×n×n

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

HalvedCube

(poly=Factor@Table[GraphData[{"HalvedCube",n},"EdgeCoverPolynomial"][x],{n,k0=2,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["XXX"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Helm

(poly=Factor@Table[GraphData[{"Helm",n},"EdgeCoverPolynomial"][x],{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^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["Helm"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Helm"/.GraphData[#,"NotationRules"]},-(((x (1+x)))^n)+(((x (((1+x))^2)))^n)]]=!=0&]

Hypercube

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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]

Select[GraphData["XXX"],Expand[GraphData[#,"DominationPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Keller

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

(poly=Factor@Table[GraphData[{"Keller",n},"EdgeCoverPolynomial"][x],{n,k0=1,1}])//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^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["XXX"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="XXX"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Knight n×n

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

(poly=Factor@Table[GraphData[{"Knight",{n,n}},"EdgeCoverPolynomial"][x],{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]]

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

Ladder

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

(poly=Factor@Table[GraphData[{"Ladder",n},"EdgeCoverPolynomial"][x],{n,k0=1,11}])//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^(n0-1))FindGeneratingFunction[poly,z]]

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

Select[GraphData["Ladder"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Ladder"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

MoebiusLadder

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

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

Simplify[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]

Odd

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

Mycielski

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

Path

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

(poly=Select[Table[GraphData[{"Path",n},"EdgeCoverPolynomial"][x],{n,n0=1,10}],FreeQ[#,Missing|GraphData]&]//Quiet)//Column

FindLinearRecurrence

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

Factor/@LinearRecurrence[coef,Take[poly,Length[coef]],10]//Column

Generating Function

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

...wrong...: bug(322287)

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0&&n∈Integers&&x∈Reals]/.n->n-1

gf=-((x (z^2))/(-1+x z+x (z^2)))

Factor/@Series[gf,{z,0,5}]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0&&n∈Integers&&x∈Reals]

RSolve

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

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

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

Sum

Factor/@Table[Sum[Binomial[k-1,n-k-1](x^k),{k,n-1}],{n,10}]//Column

bug(322284)

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

Subtract@@@Table[{x Binomial[0,-2+n] HypergeometricPFQ[{1,1,2-n},{(3/2)-(n/2),2-(n/2)},-(x/4)],Sum[Binomial[k-1,n-k-1](x^k),{k,n-1}]},{n,10}]//FullSimplify

Prism

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

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

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

SierpinskiCarpet

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

SierpinskiSieve

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

SierpinskiTetrahedron

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

Star

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

(poly=Select[Table[GraphData[{"Star",n},"EdgeCoverPolynomial"][x],{n,n0=3,20}],FreeQ[#,Missing|GraphData]&]//Quiet)

FindLinearRecurrence

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

Factor/@LinearRecurrence[coef,Take[poly,Length[coef]],10]//Column

Factor/@LinearRecurrence[coef,{1,x},10]//Column

Generating Function

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

Factor/@Series[%,{z,0,5}]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0&&n∈Integers&&x∈Reals]

RSolve

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

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

Sun

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["Sun"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Sun"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Sunlet

(poly=Factor@Table[GraphData[{"Sunlet",n},"EdgeCoverPolynomial"][x],{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^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["Sunlet"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Sunlet"/.GraphData[#,"NotationRules"]},(((x (1+x)))^n)]]=!=0&]

Transposition

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

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

Trapezohedron

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

FindLinearRecurrence[DeleteMissing@poly]//Head

TriangularGrid

(poly=Factor@Table[GraphData[{"TriangularGrid",n},"EdgeCoverPolynomial"][x],{n,k0=1,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["Sunlet"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Sunlet"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

TriangularHoneycombAcuteKnight

(poly=Factor@Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"EdgeCoverPolynomial"][x],{n,k0=1,9}])//Column

coef=Factor/@FindLinearRecurrence[poly]

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

coef=Factor/@FindPolynomialRecurrence[poly,5]

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

Select[GraphData["Sunlet"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Sunlet"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

TriangularHoneycombObtuseKnight

(poly=Factor@Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"EdgeCoverPolynomial"][x],{n,k0=3,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^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["Sunlet"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Sunlet"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

TriangularHoneycombQueen

(poly=Factor@Table[GraphData[{"TriangularHoneycombQueen",n},"EdgeCoverPolynomial"][x],{n,k0=1,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

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

Select[GraphData["Sunlet"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Sunlet"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Web

(poly=Factor@Table[GraphData[{"Web",n},"EdgeCoverPolynomial"][x],{n,k0=3,7}])//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^(n0-1))FindGeneratingFunction[poly,z]]

Select[GraphData["Web"],Expand[GraphData[#,"EdgeCoverPolynomial"][x]-With[{n="Web"/.GraphData[#,"NotationRules"]},(2^(-n)) (((((x^(3/2)) (1+x) ((Sqrt[x]) (2+x)-(Sqrt[4+x (8+x (4+x))]))))^n)+((((x^(3/2)) (1+x) ((Sqrt[x]) (2+x)+(Sqrt[4+x (8+x (4+x))]))))^n))]]=!=0&]

Wheel

Entity["Graph",{"Wheel",n}]["EdgeCoverPolynomial"]

(poly=Select[Table[GraphData[{"Wheel",n},"EdgeCoverPolynomial"][x],{n,n0=4,20}],FreeQ[#,Missing|GraphData]&]//Quiet)//Column

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

FindLinearRecurrence

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

Factor/@LinearRecurrence[coef,Take[poly,Length[coef]],10]//Column

Factor/@LinearRecurrence[coef,{0,x (1+x),(x^2) (5+4 x+(x^2)),(x^2) (3+16 x+15 (x^2)+6 (x^3)+(x^4))},10]//Column

Generating Function

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

Factor/@Series[%,{z,0,5}]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0&&n∈Integers&&x∈Reals]

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

RSolve

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

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

Part1

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

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

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

Part2

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

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