Vertex Cover Polynomial

Author

Eric W. Weisstein
February 22, 2017

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

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

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

Special Cases

Template

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

Andasfai

Select[GraphData["Andrasfai"],Head[GraphData[#,"VertexCoverPolynomial"]]===Missing&]

poly=Table[GraphData[{"Andrasfai",n},"VertexCoverPolynomial"][x],{n,10}]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

(x^(-1+2 n)) ((x^n)+(-1+3 n) (((1+x))^(-1+n)))//TraditionalForm

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

Antiprism

(poly=Table[GraphData[{"Antiprism",n},"VertexCoverPolynomial"][x],{n,3,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

Factor/@LinearRecurrence[coef,Take[poly,Length[coef]],{-1,5}]

Take[poly,3]

With[{n=Length[coef]},Factor/@LinearRecurrence[coef,Take[poly,3],3]]

Factor/@LinearRecurrence[coef,Take[poly,Length[coef]],{1,10}]==Take[poly,10]

LinearRecurrence[{x^2,2 x^3,x^4},{(x^2),(x^3) (4+x),(x^4) (3+6 x+(x^2))},3]

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

Apollonian

(poly=Factor@Table[GraphData[{"Apollonian",n},"VertexCoverPolynomial"][x],{n,4}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

ToPolynomialRecurrence[p,x,n,coef]

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

Barbell

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

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

Book

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

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

Centipede

(poly=Factor@Table[GraphData[{"Centipede",n},"VertexCoverPolynomial"][x],{n,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

(1/(Sqrt[(1+x) (1+5 x)]))(2^(-1-n)) (-(1+3 x) (((1+x-(Sqrt[(1+x) (1+5 x)])))^n)+(Sqrt[(1+x) (1+5 x)]) (((1+x-(Sqrt[(1+x) (1+5 x)])))^n)+(1+3 x) (((1+x+(Sqrt[(1+x) (1+5 x)])))^n)+(Sqrt[(1+x) (1+5 x)]) (((1+x+(Sqrt[(1+x) (1+5 x)])))^n))/.{(Sqrt[(1+x) (1+5 x)])->u,1/(Sqrt[(1+x) (1+5 x)])->1/u}//FullSimplify

Take[poly,3]

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

CocktailParty

(poly=Factor@Table[GraphData[{"CocktailParty",n},"VertexCoverPolynomial"][x],{n,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

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

Complete (Subscript[K, n])

(poly=Factor@Table[GraphData[{"Complete",n},"VertexCoverPolynomial"][x],{n,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

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

CompleteBipartite (Subscript[K, m,n])

x^p (1+x)^q+x^q (1+x)^p-x^(p+q)

Select[GraphData["CompleteBipartite"],Length[pq="CompleteBipartite"/.GraphData[#,"NotationRules"]]==2&&Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{p=pq[[1]],q=pq[[2]]},x^p (1+x)^q+x^q (1+x)^p-x^(p+q)]]=!=0&]

CompleteBipartite (Subscript[K, n,n])

FullSimplify[x^p (1+x)^q+x^q (1+x)^p-x^(p+q)]/.{p->n,q->n}

(poly=Factor@Table[GraphData[{"CompleteBipartite",{n,n}},"VertexCoverPolynomial"][x],{n,10}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

CompleteTripartite (Subscript[K, n,n,n])

FullSimplify[(x^(p+q))(((1+x))^r)+(x^(q+r)) (((1+x))^p)+(x^(r+p))(((1+x))^q)-2(x^(p+q+r))]/.{p->n,q->n,r->n}

(poly=Factor@Table[GraphData[{"CompleteTripartite",{n,n,n}},"VertexCoverPolynomial"][x],{n,6}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

Select[GraphData["CompleteTripartite"],Length[pq="CompleteTripartite"/.GraphData[#,"NotationRules"]]==3&&Equal@@pq&&Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n=pq[[1]]},-2 x^(3 n)+3 (x^2 (1+x))^n]]=!=0&]

CompleteTripartite (Subscript[K, k,m,n])

(x^(p+q))(((1+x))^r)+(x^(q+r)) (((1+x))^p)+(x^(r+p))(((1+x))^q)-2(x^(p+q+r))

Select[GraphData["CompleteTripartite"],Length[pq="CompleteTripartite"/.GraphData[#,"NotationRules"]]==3&&Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{p=pq[[1]],q=pq[[2]],r=pq[[3]]},(x^(p+q))(((1+x))^r)+(x^(q+r)) (((1+x))^p)+(x^(r+p))(((1+x))^q)-2(x^(p+q+r))]]=!=0&]

CrossedPrism

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,2n,coef]

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

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

Take[poly,3]

Select[GraphData["CrossedPrism"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="CrossedPrism"/.GraphData[#,"NotationRules"]},LinearRecurrence[
{(x^2) (2+4 x+(x^2)),-(x^4) (1+4 x+2 (x^2))},
{(x^2) (2+4 x+(x^2)),(x^4) (2+8 x+16 (x^2)+8 (x^3)+(x^4)),(x^6) (2+4 x+(x^2)) (1+4 x+14 (x^2)+8 (x^3)+(x^4))},
n/2][[-1]]]]=!=0&]

Crown

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

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

CubeConnectedCycle

(poly=Factor@Table[GraphData[{"CubeConnectedCycle",n},"VertexCoverPolynomial"][x],{n,3,5}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

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

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

Cycle (Subscript[C, n])

(poly=Factor@Table[GraphData[{"Cycle",n},"VertexCoverPolynomial"][x],{n,k0=3,10}])//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]

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

bug(308790)

...wrong...

Table[Binomial[1,-1+n] ,{n,10}]

Table[n x Binomial[1,-1+n] HypergeometricPFQ[{1,1,1-n},{(3/2)-(n/2),2-(n/2)},-(x/4)],{n,3,10}]

Limit[n x Binomial[1,-1+n] HypergeometricPFQ[{1,1,1-n},{(3/2)-(n/2),2-(n/2)},-(x/4)],n->3]

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

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

Empty (Subscript[(OverBar[K]), n])

(poly=Factor@Table[GraphData[{"Empty",n},"VertexCoverPolynomial"][x],{n,k0=1,10}])//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["Empty"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Empty"/.GraphData[#,"NotationRules"]},(((1+x))^n)]]=!=0&]

FoldedCube

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,4]

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["FoldedCube"],Expand[GraphData[#,"FoldedCube"][x]-With[{n="FoldedCube"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Gear

(poly=Factor@Table[GraphData[{"Gear",n},"VertexCoverPolynomial"][x],{n,k0=3,10}])//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["Gear"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Gear"/.GraphData[#,"NotationRules"]},(2^(-n)) ((2^n) (((x (1+x)))^n)+x ((((x (2+x-(Sqrt[x]) (Sqrt[4+x]))))^n)+(((x (2+x+(Sqrt[x]) (Sqrt[4+x]))))^n)))]]=!=0&]

Grid (Subscript[P, n])×(Subscript[P, n])

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

coef=Factor/@FindPolynomialRecurrence[poly,4]

coef=Factor/@FindPolynomialRecurrence[poly,5]

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["Grid"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Grid"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Grid (Subscript[P, n])×(Subscript[P, n])×(Subscript[P, n])

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

coef=Factor/@FindPolynomialRecurrence[poly,2]

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["Grid"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Grid"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

HalvedCube

(poly=Factor@Table[GraphData[{"HalvedCube",n},"VertexCoverPolynomial"][x],{n,k0=1,7}])//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["HalvedCube"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="HalvedCube"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Hanoi

(poly=Factor@Table[GraphData[{"Hanoi",n},"VertexCoverPolynomial"][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["Hanoi"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Hanoi"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Helm

(poly=Factor@Table[GraphData[{"Helm",n},"VertexCoverPolynomial"][x],{n,k0=3,10}])//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["Helm"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Helm"/.GraphData[#,"NotationRules"]},(2^(-n)) ((2^n) (((x (1+x)))^n)+x ((((x (1+x-(Sqrt[(1+x) (5+x)]))))^n)+(((x (1+x+(Sqrt[(1+x) (5+x)]))))^n)))]]=!=0&]

Hypercube

(poly=Factor@Table[GraphData[{"Hypercube",n},"VertexCoverPolynomial"][x],{n,k0=3,6}])//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["Hypercube"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Hypercube"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Keller

(poly=Factor@Table[GraphData[{"Keller",n},"VertexCoverPolynomial"][x],{n,k0=1,3}])//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}},"VertexCoverPolynomial"][x],{n,k0=2,10}])//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["Crown"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Crown"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Ladder

A122542

A113413

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

CoefficientList[#,x]&/@MapIndexed[#/x^#2[[1]]&,poly]

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]

SeriesCoefficient[(1-x)/(1-(1+y)*x-y*x^2),{x,0,n}]/.y->x//FullSimplify

sum{i=0..n-k,C(k+1,i)C(n-i,k)}

Table[Binomial[k+1,i]Binomial[n-i,k],{n,3},{k,n},{i,0,n-k}]

CoefficientList[CoefficientList[Series[1/(1-2 x/(1+x)-y x),{x,0,10},{y,0,10}],x],y]

SeriesCoefficient[(1-x)/(1-(1+y)*x-y*x^2),{x,0,n},{y,0,m}]

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

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

LadderRung

(poly=Factor@Table[GraphData[{"LadderRung",n},"VertexCoverPolynomial"][x],{n,k0=1,10}])//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["LadderRung"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="LadderRung"/.GraphData[#,"NotationRules"]},(((x (2+x)))^n)]]=!=0&]

Lattice n×n

(poly=Factor@Table[GraphData[{"Lattice",{n,n}},"VertexCoverPolynomial"][x],{n,k0=1,10}])//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["Lattice"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Lattice"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

MoebiusLadder (Subscript[M, n])

(poly=Factor@Table[GraphData[{"MoebiusLadder",n},"VertexCoverPolynomial"][x],{n,k0=3,10}])//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]

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

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

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

Mycielski

(poly=Factor@Table[GraphData[{"Mycielski",n},"VertexCoverPolynomial"][x],{n,k0=1,7}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,3]

coef=Factor/@FindPolynomialRecurrence[poly,4]

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["Mycielski"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Mycielski"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Odd (Subscript[O, n])

(poly=Factor@Table[GraphData[{"Odd",n},"VertexCoverPolynomial"][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["Odd"],Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Odd"/.GraphData[#,"NotationRules"]},XXX]]=!=0&]

Pan

(poly=Factor@Table[GraphData[{"Pan",n},"VertexCoverPolynomial"][x],{n,k0=3,10}])//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["Pan"],FullSimplify@Expand[GraphData[#,"VertexCoverPolynomial"][x]-With[{n="Pan"/.GraphData[#,"NotationRules"]},(2^(-1-n)) (-(Sqrt[(x/(4+x))]) (((x-(Sqrt[x]) (Sqrt[4+x])))^n)+(1+2 x) (((x-(Sqrt[x]) (Sqrt[4+x])))^n)+(Sqrt[(x/(4+x))]) (((x+(Sqrt[x]) (Sqrt[4+x])))^n)+(1+2 x) (((x+(Sqrt[x]) (Sqrt[4+x])))^n))]]=!=0&]

Path

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

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

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

bug(308790)

Table[Binomial[1,n] HypergeometricPFQ[{1,2,-n},{1-(n/2),(3/2)-(n/2)},-(x/4)],{n,2,5}]

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

PermutationStar

poly=Table[GraphData[{"PermutationStar",n},"VertexCoverPolynomial"][x],{n,5}]

r=FindLinearRecurrence[p]

Prism

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

TeXForm[(2^(-n)) ((((-2))^n) (x^n)+(((x (1+x-(Sqrt[1+x (6+x)]))))^n)+(((x (1+x+(Sqrt[1+x (6+x)]))))^n))]

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

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

SierpinskiCarpet

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

SierpinskiSieve

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

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

Star

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

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

Sun

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

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

Sunlet

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

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

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

Tetrahedral

(poly=Factor@Table[GraphData[{"Tetrahedral",n},"VertexCoverPolynomial"][x],{n,k0=6,9}])//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]

TorusGrid n×n

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

coef=Factor/@FindLinearRecurrence[poly]

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]

Transposition

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

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

Triangular

(poly=Factor@Table[GraphData[{"Triangular",n},"VertexCoverPolynomial"][x],{n,k0=2,20}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,9]

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]

TriangularGrid

(poly=Factor@Table[GraphData[{"TriangularGrid",n},"VertexCoverPolynomial"][x],{n,k0=1,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},"VertexCoverPolynomial"][x],{n,k0=3,15}])//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]

Wheel

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

Algorithm

<<MathWorld`Graphs`

IndependencePolynomial: Subsets

DeleteCases[Monitor[{
#,
Expand@GraphData[g=#,"VertexCoverPolynomial"][x],
VertexCoverPolynomial[GraphData[#],x]//Expand
}&/@GraphData[;;7],g],{_,x_,x_}]//Timing

IndependencePolynomial: IGraphM

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

IndependencePolynomial: IGraphMIncremental

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

IndependencePolynomial: VertexDeletion

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