Independence Polynomial

Author

Eric W. Weisstein
December 10, 2023

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

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

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

Co-independence graphs

l=Monitor[Sort[{GetGraphData[#,"IndependencePolynomial"][x],g=#}&/@GetGraphData[All]],g];//Timing

Length[co=Select[Split[l,First[#1]==First[#2]&],Length[#]>1&]]

ll=Sort[{GetGraphData[#[[1,2]],"V"],#[[1,1]],#[[All,2]]}&/@co];

TableForm[Take[Most[ll],-5],TableDepth->2]

TableForm[Take[ll,30],TableDepth->2]

Properties

I(Tree) is unimodal

Select[GraphData["Tree"],Head[i=GraphData[#,"IndependencePolynomial"]]=!=Missing&&UnimodalQ[i[x],x]=!=True&]

I((Subscript[K, 1,3])-free) is log-concave

Select[GraphData["ClawFree"],Head[i=GraphData[#,"IndependencePolynomial"]]=!=Missing&&LogConcaveQ[i[x],x]=!=True&]

Parametrized families

Andasfai

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

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

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

RSolve[{p[n,x]==(3+2x)p[n-1,x]+(-3-4x-x^2)p[n-2,x]+(1+2x+x^2)p[n-3,x],
p[1,x]==1+2 x,
p[2,x]==1+5 x+5 (x^2),
p[3,x]==(1+2 x) (1+6 x+4 (x^2))},p[n,x],n]//FullSimplify

Antiprism

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

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

FindSequenceFunction[Coefficient[poly,x,2],n-2]//Factor

FindSequenceFunction[Coefficient[Rest@poly,x,3],n-3]//Factor

FindSequenceFunction[Coefficient[Drop[poly,2],x,4],n-4]//Factor

FindSequenceFunction[Coefficient[Drop[poly,3],x,5],n-5]//Factor

FindSequenceFunction[Coefficient[Drop[poly,4],x,6],n-6]//Factor

FindSequenceFunction[Coefficient[Drop[poly,5],x,7],n-7]//Factor

FindSequenceFunction[Coefficient[Drop[poly,6],x,8],n-8]//Factor

FindSequenceFunction[Coefficient[Drop[poly,7],x,9],n-9]//Factor

Table[Pochhammer[n,5]/8,{n,5}]{1,1,1,4,6}

FindSequenceFunction[Coefficient[Drop[poly,8],x,10],n-10]//Factor

FindSequenceFunction[{6,15,90,315,2520,11340},n]

Table[
(1/(k!))Product[n-i,{i,k+1,Floor[(3k-1)/2]}]n Product[2n-i,{i,2k+1,3k-1,2}](x^k),{k,7}]//Column

Table[1+2n x+
n(2n-5)(x^2)+
(2/3) (-4+n) n (-7+2 n)(x^3)+
(1/6) (-5+n) n (-11+2 n) (-9+2 n)(x^4)+
(1/15) (-7+n) (-6+n) n (-13+2 n) (-11+2 n)(x^5)+
(1/90) (-8+n) (-7+n) n (-17+2 n) (-15+2 n) (-13+2 n)(x^6)+
(1/315) (-10+n) (-9+n) (-8+n) n (-19+2 n) (-17+2 n) (-15+2 n)(x^7),
{n,3,15}]//Column

FindSequenceFunction[{6,15,90,315},n]

Table

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]

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

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

Apollonian

p=Table[GraphData[{"Apollonian",n},"IndependencePolynomial"][x],{n,5}]

r=Factor/@FindLinearRecurrence[p]

FindPolynomialRecurrence[p,2]

Barbell

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

Bishop n×n

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

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

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

BlackBishop n×n

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

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

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

Do[Print[{gn={"BlackBishop",{n,n}},IndependencePolynomial[GraphData[gn],x]//Timing}],{n,20}]

Book

p=Table[GraphData[{"Book",n},"IndependencePolynomial"][x],{n,3,14}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

RSolve[{p[n,x]==(2+3x)p[n-1,x]+(-1-3x-2x^2)p[n-2,x],p[3,x]==1+8 x+18 (x^2)+14 (x^3)+2 (x^4),p[4,x]==1+10 x+32 (x^2)+44 (x^3)+24 (x^4)+2 (x^5)},p[n,x],n]//FullSimplify

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

Camel n×n

Table[GraphData[{"Camel",{n,n}},"Connected"],{n,20}]

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

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

Do[Print[{k,FindGeneratingFunction[DeleteMissing@Drop[p,k],z]//Head//Timing}],{k,0,6}]

Centipede

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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

p=Table[GraphData[{"CocktailParty",n},"IndependencePolynomial"][x],{n,10}]

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==-p[-2+n,x]+2 p[-1+n,x],p[1,x]==(((1+x))^2),p[2,x]==1+4 x+2 (x^2)},p[n,x],n]//FullSimplify

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

Complete

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

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}}]["IndependencePolynomial"][x]

CompleteBipartite n×n

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

p=Table[GraphData[{"CompleteBipartite",{n,n}},"IndependencePolynomial"][x],{n,15}]

r=Factor/@FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(-1-x) p[-2+n,x]+(2+x) p[-1+n,x],p[1,x]==1+2 x,p[2,x]==1+4 x+2 (x^2)},p[n,x],n]

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

CompleteTripartite k×m×n

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

CompleteTripartite n×n×n

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

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

p=Table[GraphData[{"CrossedPrism",n},"IndependencePolynomial"][x],{n,4,20,2}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(-2 (x^2)-4 (x^3)-(x^4)) p[-2+n,x]+(1+4 x+2 (x^2)) p[-1+n,x],p[2,x]==1+8 x+16 (x^2)+8 (x^3)+2 (x^4),p[3,x]==(1+4 x+2 (x^2)) (1+8 x+14 (x^2)+4 (x^3)+(x^4))},p[n,x],n]//FullSimplify

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

Crown

p=Table[GraphData[{"Crown",n},"IndependencePolynomial"][x],{n,3,10}]

r=Factor/@FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(1+x) p[-3+n,x]+(-3-2 x) p[-2+n,x]+(3+x) p[-1+n,x],p[3,x]==(1+2 x) (1+4 x+(x^2)),p[4,x]==1+8 x+16 (x^2)+8 (x^3)+2 (x^4),p[5,x]==1+10 x+25 (x^2)+20 (x^3)+10 (x^4)+2 (x^5)},p[n,x],n]//FullSimplify

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

CubeConnectedCycle

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

p=Table[GraphData[{"CubeConnectedCycle",n},"IndependencePolynomial"][x],{n,3,5}]

FindLinearRecurrence[p]

FindPolynomialRecurrence[p,2]

Cycle

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

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

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

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

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

RSolve[{p[n,x]==p[n-1,x]+x p[n-2,x],p[3,x]==1+3 x,p[4,x]==1+4 x+2 (x^2)},p[n,x],n]

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

FullSimplify[Table[%,{n,10}]]

DorogovtsevGoltsevMendes

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

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

Empty

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

FibonacciCube

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

FindLinearRecurrence[poly]//Head//Timing

FoldedCube

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

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

Gear

p=Table[GraphData[{"Gear",n},"IndependencePolynomial"][x],{n,3,20}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{
p[n,x]==((x^2)+(x^3)) p[-3+n,x]+(-1-3 x-3 (x^2)) p[-2+n,x]+(2+3 x) p[-1+n,x],
p[3,x]==1+7 x+12 (x^2)+5 (x^3)+(x^4),
p[4,x]==1+9 x+24 (x^2)+22 (x^3)+6 (x^4)+(x^5),
p[5,x]==1+11 x+40 (x^2)+60 (x^3)+35 (x^4)+7 (x^5)+(x^6)},p[n,x],n]//FullSimplify

(2^(-n)) ((2^n) x (((1+x))^n)+(((1+2 x-(Sqrt[1+4 x])))^n)+(((1+2 x+(Sqrt[1+4 x])))^n))/.(Sqrt[1+4 x])->t//Expand//Simplify

Giraffe n×n

Table[GraphData[{"Giraffe",{n,n}},"Connected"],{n,20}]

p=Table[GraphData[{"Giraffe",{n,n}},"IndependencePolynomial"],{n,20}]/.f_Function:>f[x]

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

FindLinearRecurrence[DeleteMissing@Drop[p,5]]

Goldberg

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

2+Length@DeleteMissing@poly

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

Grid m×n

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

Grid n×n

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

(poly=Factor@Table[GraphData[{"Grid",{n,n}},"IndependencePolynomial"][x],{n,k0=1,kmax=10}]/.f_Function:>f[x])//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}]

Grid n×n×n

Grid k×m×n

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

Grid m×n

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

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

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

HalvedCube

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

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

Hanoi

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

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

Helm

p=Table[GraphData[{"Helm",n},"IndependencePolynomial"][x],{n,3,20}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(-x-2 (x^2)-(x^3)) p[-3+n,x]+(-1-x) p[-2+n,x]+(2+2 x) p[-1+n,x],
p[3,x]==(((1+x))^2) (1+5 x+(x^2)),p[4,x]==(((1+x))^2) (1+7 x+9 (x^2)+(x^3)),p[5,x]==(((1+x))^3) (1+8 x+13 (x^2)+(x^3))},p[n,x],n]//FullSimplify

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

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

Hypercube

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

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

Keller

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

(poly=Factor@Table[GraphData[{"Keller",n},"IndependencePolynomial"][x],{n,k0=1,3}])//Column

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,2]

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

p=Factor/@Table[GraphData[{"KingsTour",{n,n}},"IndependencePolynomial"][x],{n,2,9}]

FindLinearRecurrence[p]

Factor/@FindPolynomialRecurrence[p,2]

Knight m×n

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

Knight n×n

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

Ladder

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

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

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

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

Reverse/@CoefficientList[Table[(((2^(-1-n)) ((((1+x-(Sqrt[1+6 x+(x^2)])))^n) (-3-x+(Sqrt[1+6 x+(x^2)]))+(((1+x+(Sqrt[1+6 x+(x^2)])))^n) (3+x+(Sqrt[1+6 x+(x^2)]))))/(Sqrt[1+6 x+(x^2)])),{n,0,10}],x]

A035607

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

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

Factor/@FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

CoefficientList[#,x]&/@Take[p,6]

RSolve[{p[n,x]==(x+1)p[n-1,x]+x p[n-2,x],p[1,x]==1+2 x,p[2,x]==1+4 x+2 (x^2)},p[n,x],n]//FullSimplify

expr1=(2^(-1-n)) (-(1+3 x) (((1+x-(Sqrt[1+x (6+x)])))^n)+(Sqrt[1+x (6+x)]) (((1+x-(Sqrt[1+x (6+x)])))^n)+(1+3 x) (((1+x+(Sqrt[1+x (6+x)])))^n)+(Sqrt[1+x (6+x)]) (((1+x+(Sqrt[1+x (6+x)])))^n));

expr2=(2^(-1-n)) (((Sqrt[1+x (6+x)]) -(1+3 x) )(((1+x-(Sqrt[1+x (6+x)])))^n)+((1+3 x)+(Sqrt[1+x (6+x)]) ) (((1+x+(Sqrt[1+x (6+x)])))^n));

expr1-expr2//FullSimplify

Factor[1+x (6+x)]

expr2/.(Sqrt[1+x (6+x)])->s//TraditionalForm

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

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

A035607

Factor/@Series[(1+x)/(1-x-x*y-x^2*y),{x,0,5}]

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

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

LadderRung

p=Table[GraphData[{"LadderRung",n},"IndependencePolynomial"][x],{n,20}]

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

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

LucasCube

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

MoebiusLadder

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

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

CoefficientList[Take[poly,5],x]

r=FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(x^2) p[-3+n,x]+(2 x+(x^2)) p[-2+n,x]+p[-1+n,x],p[3,x]==1+6 x+6 (x^2)+2 (x^3),p[4,x]==(1+2 x) (1+6 x+4 (x^2)),p[5,x]==1+10 x+30 (x^2)+30 (x^3)+10 (x^4)+2 (x^5)},p[n,x],n]//FullSimplify

p-Table[(2^(-n)) (-(2^n) (((-x))^n)+(((1+x-(Sqrt[1+x (6+x)])))^n)+(((1+x+(Sqrt[1+x (6+x)])))^n)),{n,3,12}]//Expand

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

Mycielski

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

p=Table[GraphData[{"Mycielski",n},"IndependencePolynomial"][x],{n,7}]

r=FindLinearRecurrence[p]

r=FindPolynomialRecurrence[p,2]

Odd

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

p=Table[GraphData[{"Odd",n},"IndependencePolynomial"][x],{n,2,4}]

r=Factor/@FindLinearRecurrence[p]

r=FindPolynomialRecurrence[p,2]

Pan

p=Table[GraphData[{"Pan",n},"IndependencePolynomial"][x],{n,3,7}]

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==x p[-2+n,x]+p[-1+n,x],
p[3,x]==1+4 x+2 (x^2),
p[4,x]==(1+x) (1+4 x+(x^2))},p[n,x],n]//FullSimplify

(2^(-1-n)) ((2+x) (((1-(Sqrt[1+4 x])))^n)-((x (((1-(Sqrt[1+4 x])))^n))/(Sqrt[1+4 x]))+(2+x) (((1+(Sqrt[1+4 x])))^n)+((x (((1+(Sqrt[1+4 x])))^n))/(Sqrt[1+4 x])))/.{(Sqrt[1+4 x])->t,1/(Sqrt[1+4 x])->1/t}//FullSimplify

Path

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

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

FullSimplify[Sum[Binomial[n+1-j,j]x^j,{j,0,Floor[(n+1)/2]}],n∈Integers&&n>0]

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

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

RSolve[{p[n,x]==p[n-1,x]+x p[n-2,x],p[1,x]==1+x,p[2,x]==1+2 x},p[n,x],n]//FullSimplify

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

Pell

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

PermutationStar

p=Table[GraphData[{"PermutationStar",n},"IndependencePolynomial"][x],{n,5}]

r=FindLinearRecurrence[p]

Prism

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

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

r=FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(x^2) p[-3+n,x]+(2 x+(x^2)) p[-2+n,x]+p[-1+n,x],p[3,x]==1+6 x+6 (x^2),p[4,x]==1+8 x+16 (x^2)+8 (x^3)+2 (x^4),p[5,x]==1+10 x+30 (x^2)+30 (x^3)+10 (x^4)},p[n,x],n]//FullSimplify

p-Table[(2^(-n)) ((2^n) (((-x))^n)+(((1+x-(Sqrt[1+x (6+x)])))^n)+(((1+x+(Sqrt[1+x (6+x)])))^n)),{n,3,12}]//Expand

Queen n×n

A348129

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

Length@DeleteMissing@poly

Rook n×n

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

FindLinearRecurrence[poly]

FindGeneratingFunction[poly,z]

RookComplement n×n

(poly=Factor@Table[GraphData[{"RookComplement",{n,n}},"IndependencePolynomial"],{n,k0=1,10}]/.f_Function:>f[x])//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^(k0-1))FindGeneratingFunction[poly,z]]

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

SierpinskiCarpet

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

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

SierpinskiSieve

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

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

Star

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

p=Table[GraphData[{"Star",n},"IndependencePolynomial"][x],{n,3,20}]

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

RSolve[{p[n,x]==(2+x)p[n-1,x]+(-1-x)p[n-2,x],p[3,x]==1+3 x+(x^2),p[4,x]==1+4 x+3 (x^2)+(x^3)},p[n,x],n]//FullSimplify

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

Sun

p=Table[GraphData[{"Sun",n},"IndependencePolynomial"][x],{n,3,14}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

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

p-Table[(((1+x))^(n-2))(1+(n+2)x+(x^2)),{n,3,14}]

Sunlet

p=Table[GraphData[{"Sunlet",n},"IndependencePolynomial"][x],{n,3,14}]

r=Factor/@FindLinearRecurrence[p]

Map[Factor,ToPolynomialRecurrence[poly,x,n,r],{2}]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

ToPolynomialRecurrence[p,x,n,r]

RSolve[{p[n,x]==(x+(x^2)) p[-2+n,x]+(1+x) p[-1+n,x],p[3,x]==(((1+x))^2) (1+4 x),
p[4,x]==(((1+x))^2) (1+6 x+7 (x^2))
},p[n,x],n]//FullSimplify

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

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

rules=Table[GraphData[{"Sunlet",n},"#"]->Factor[Expand[(2^(-n)) ((((1+x-(Sqrt[(1+x) (1+5 x)])))^n)+(((1+x+(Sqrt[(1+x) (1+5 x)])))^n))]],{n,3,20}]

Tetrahedral

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

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

TorusGrid n×n

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

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

2+Length@DeleteMissing@poly

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

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

Transposition

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

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

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

Triangular

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

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

Table[HermiteH[n,(1/(Sqrt[-2x]))](((-(x/2)))^(n/2)),{n,10}]//Factor//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]]

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

A100861

Table[n!/(k!(n-2k)!*2^k),{n,5},{k,0,n}]

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

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

Take[poly,9]

Table[(-I*Sqrt[x/2])^n*HermiteH[n,I/Sqrt[2x]],{n,2,10}]//Expand

FullSimplify[(-I*Sqrt[x/2])^n*HermiteH[n,I/Sqrt[2x]]]

SeriesCoefficient[Exp[z+t z^2/2],{z,0,n}]//FullSimplify

TriangularGrid

A239567

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

Length@DeleteMissing@poly

FindLinearRecurrence[DeleteMissing@Drop[poly,1]]//Head//Timing

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

TriangularHoneycombAcuteKnight

(poly=Factor@Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"IndependencePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column[#,Dividers->All]&//TraditionalForm

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

TriangularHoneycombBishop

A008278

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

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

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

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

GeneratingFunction[x^n BellB[n,1/x],x,n]//Timing

TriangularHoneycombObtuseKnight

(poly=Factor@Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"IndependencePolynomial"],{n,k0=1,kmax=20}]/.f_Function:>f[x])//Column[#,Dividers->All]&//TraditionalForm

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

TriangularHoneycombQueen

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

Length@DeleteMissing@poly

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

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

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

Do[Print[{{"TriangularHoneycombQueen",n},IndependencePolynomial[TriangularHoneycombQueenGraph[n],x]//Timing}],{n,20}]

TriangularHoneycombRook

(poly=Factor@Table[GraphData[{"TriangularHoneycombRook",n},"IndependencePolynomial"],{n,k0=1,kmax=10}]/.f_Function:>f[x])//Column[#,Dividers->All]&//TraditionalForm

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

Product[k x+1,{k,n}]//FullSimplify

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

Web

(poly=Factor@Table[GraphData[{"Web",n},"IndependencePolynomial"][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]//Timing

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

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

Wheel

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

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

CoefficientList[Take[poly,7],x]

r=FindLinearRecurrence[p]

ToPolynomialRecurrence[poly,x,n,r]/.poly[n_,x_]:>Subscript[HoldForm[p],n][x]//TraditionalForm

p=.

RSolve[{p[n,x]==2p[n-1,x]+(-1+x)p[n-2,x]-x p[n-3,x],p[4,x]==1+4 x,p[5,x]==1+5 x+2 (x^2),p[6,x]==1+6 x+5 (x^2)},p[n,x],n]//FullSimplify

(1/x)(2^(-1-n)) ((2^(1+n)) (x^2)-(((1-(Sqrt[1+4 x])))^n)-(Sqrt[1+4 x]) (((1-(Sqrt[1+4 x])))^n)-(((1+(Sqrt[1+4 x])))^n)+(Sqrt[1+4 x]) (((1+(Sqrt[1+4 x])))^n))/.{(Sqrt[1+4 x])->t,1/(Sqrt[1+4 x])->1/t}//FullSimplify

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

WhiteBishop n×n

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

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

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

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

Zebra n×n

Table[GraphData[{"Zebra",{n,n}},"Connected"],{n,20}]

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

Length@DeleteMissing@poly

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

FindLinearRecurrence[DeleteMissing@Drop[poly,5]]

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

Algorithms

GraphData[{"Keller",2},"IndependencePolynomial"][x]//Expand

IGraphM

IndependencePolynomial[GraphData[{"Keller",3}],x,Method->"IGraphM",Debug->True]//Timing

IGraphMIncremental

IndependencePolynomial[GraphData[{"Keller",3}],x,Method->"IGraphMIncremental",Debug->True]//Timing

IndependentVertexSetQ over all subsets

IP[g_System`Graph,x_]:=Total[#2 x^#&@@@Tally[Length/@Select[Subsets[VertexList[g]],IndependentVertexSetQ[g,#]&]]]

IP[System`Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1,2\[DirectedEdge]1,3\[DirectedEdge]2,1\[DirectedEdge]3}],x]

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;15],{_,0}],g]//Timing

IndependentVertexSetQ with subsets to α

IP[g_System`Graph,x_]:=Module[{alpha=Length[Flatten[FindIndependentVertexSet[g]]]},Total[#2 x^#&@@@Tally[Length/@Select[Subsets[VertexList[g],{0,alpha}],IndependentVertexSetQ[g,#]&]]]]

IP[System`Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1,2\[DirectedEdge]1,3\[DirectedEdge]2,1\[DirectedEdge]3}],x]

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;15],{_,0}],g]//Timing

VertexDeletion (No caching)

Quit

GraphData[];

rp[g_,x_]:=Replace[VertexList[g],{{}->1,{v_,___}:>Expand[rp[VertexDelete[g,v],x]+x rp[VertexDelete[g,Append[AdjacencyList[g,v],v]],x]]}]

IP[g_System`Graph,x_]:=Internal`InheritedBlock[{rp},rp[g,x]]

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;10],{_,0}],g]//Timing

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;15],{_,0}],g]//Timing

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IndependencePolynomial[GraphData[#],x,"Caching"->False]]}&/@GraphData[;;15],{_,0}],g]//Timing

VertexDeletion with Caching

Quit

GraphData[];

rp[g_,x_]:=rp[g,x]=Replace[VertexList[g],{{}->1,{v_,___}:>Expand[rp[VertexDelete[g,v],x]+x rp[VertexDelete[g,Append[AdjacencyList[g,v],v]],x]]}]

IP[g_System`Graph,x_]:=Internal`InheritedBlock[{rp},rp[g,x]]

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;10],{_,0}],g]//Timing

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;15],{_,0}],g]//Timing

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IndependencePolynomial[GraphData[#],x,"Caching"->True]]}&/@GraphData[;;15],{_,0}],g]//Timing

VertexDeletion with Caching + Canonicalization

Quit

GraphData[];

rp[g_,x_]:=rp[g,x]=Replace[VertexList[g],{{}->1,{v_,___}:>Expand[rp[CanonicalGraph@VertexDelete[g,v],x]+x rp[CanonicalGraph@VertexDelete[g,Append[AdjacencyList[g,v],v]],x]]}]

IP[g_System`Graph,x_]:=Internal`InheritedBlock[{rp},rp[g,x]]

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;10],{_,0}],g]//Timing

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;15],{_,0}],g]//Timing

VertexDeletion with Caching + Canonicalization + initial canonicalization

rp[g_,x_]:=rp[g,x]=Replace[VertexList[g],{{}->1,{v_,___}:>Expand[rp[CanonicalGraph@VertexDelete[g,v],x]+x rp[CanonicalGraph@VertexDelete[g,Append[AdjacencyList[g,v],v]],x]]}]

IP[g_System`Graph,x_]:=Internal`InheritedBlock[{rp},rp[g,x]]

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[CanonicalGraph@GraphData[#],x]]}&/@GraphData[;;10],{_,0}],g]//Timing

Monitor[DeleteCases[{g=#,Expand[GraphData[#,"IndependencePolynomial"][x]-IP[GraphData[#],x]]}&/@GraphData[;;15],{_,0}],g]//Timing

From MaximalIndependentVertexSets

def=Sort[GraphData[#,{"IndependenceNumber","#"}]&/@GraphData["MaximalIndependentVertexSets","Defined"]]

DeleteCases[Monitor[{g=#,IndependencePolynomial[GraphData[#,"MaximalIndependentVertexSets"],x],Expand@GraphData[#,"IndependencePolynomial"][x]}&/@Select[def,#[[1]]<10&][[All,2]],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,IndependencePolynomial[GraphData[#,"MaximalIndependentVertexSets"],x],Expand@GraphData[#,"IndependencePolynomial"][x]}&/@Select[def,#[[1]]<20&][[All,2]],g],{_,x_,x_}]//Timing

DeleteCases[Monitor[{g=#,IndependencePolynomial[GraphData[#,"MaximalIndependentVertexSets"],x],Expand@GraphData[#,"IndependencePolynomial"][x]}&/@Select[def,#[[1]]<25&][[All,2]],g],{_,x_,x_}]//Timing