Domination Polynomial

Author

Eric W. Weisstein
January 25, 2024

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

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

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

Families

Alkane

(poly=Factor/@Table[GraphData[{"Alkane",n},"DominationPolynomial"],{n,10}]/.f_Function:>f[x])//Column

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

AlternatingGroupGraph

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

Andrasfai

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

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

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

Antelope n×n

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

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

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

Antiprism

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

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

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

FindLinearRecurrence[Take[poly,11]]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==(x^2) (Subscript[p, n-5])(x)+(x^2) (Subscript[p, n-4])(x)+(x^2) (Subscript[p, n-3])(x)+(x+2) x (Subscript[p, n-2])(x)+(x+2) x (Subscript[p, n-1])(x)]

soln=RSolve[Prepend[Table[p[k+k0-1,x]==poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n]

ByteCount[soln]

(simp=Simplify[soln,n∈Integers&&n>2])//Timing

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

Apollonian

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

Barbell

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==-((x^2)+3 x+3) (x+1) (Subscript[p, n-2])(x)+((x^2)+3 x+3) (Subscript[p, n-1])(x)+(((x+1))^3) (Subscript[p, n-3])(x)]

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]

rules=(#->With[{n="Barbell"/.GraphData[#,"NotationRules"]},(((-1+(((1+x))^n)))^2)])&/@GraphData["Barbell",32;;]

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

Bishop n×n

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

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

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

BlackBishop n×n

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

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

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

Book

(poly=Factor@Table[GraphData[{"Book",n},"DominationPolynomial"][x],{n,k0=1,14}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==(x^2) (x+2) (((x+1))^2) (Subscript[p, n-3])(x)+(2 (x^2)+5 x+1) (Subscript[p, n-1])(x)-x ((x^3)+6 (x^2)+9 x+3) (Subscript[p, n-2])(x)]

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]

rules=(#->With[{n="Book"/.GraphData[#,"NotationRules"]},-2 (x^n)+(x^2) (((1+x))^(2 n))+(((x (2+x)))^n) (1+2 x)])&/@GraphData["Book",32;;]

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

Bruhat

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

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

Camel n×n

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

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

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

Centipede

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

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

FindLinearRecurrence[poly]

CocktailParty

(poly=Factor@Table[GraphData[{"CocktailParty",n},"DominationPolynomial"][x],{n,k0=1,15}])//Column

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==-(2 (x^2)+4 x+3) (Subscript[p, n-2])(x)+((x^2)+2 x+3) (Subscript[p, n-1])(x)+(((x+1))^2) (Subscript[p, n-3])(x)]

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]

rules=(#->With[{n="CocktailParty"/.GraphData[#,"NotationRules"]},-1-2 n x+(((1+x))^(2 n))])&/@GraphData["CocktailParty",32;;]

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

Complete

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==(x+2) (Subscript[p, n-1])(x)-(x+1) (Subscript[p, n-2])(x)]

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["Complete"],Expand[GraphData[#,"DominationPolynomial"][x]-With[{n="Complete"/.GraphData[#,"NotationRules"]},-1+(((1+x))^n)]]=!=0&]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["DominationPolynomial"][x]

CompleteBipartite n×n

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

FullSimplify[((((1+x))^m)-1)((((1+x))^n)-1)+(x^m)+(x^n)/.m->n]

Total[#2x^#&@@@Tally[Length/@FindDominatingSet[GraphData["K3,4"],∞,All]]]

Expand[With[{m=3,n=4},((((1+x))^m)-1)((((1+x))^n)-1)+(x^m)+(x^n)]]

l=DeleteCases[{#,{0,Module[{m,n},{m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"];((((1+x))^m)-1)((((1+x))^n)-1)+(x^m)+(x^n)]}}&/@GraphData["CompleteBipartite"],{{"Star"|"Path",_}|"ClawGraph",_}]

GraphData["CompleteBipartite"],{{"Star"|"Path",_}|"ClawGraph",_}]

Select[GraphData["CompleteBipartite"],Min@@({m,n}="CompleteBipartite"/.GraphData[#,"NotationRules"])>1&&Expand[GraphData[#,"DominationPolynomial"][x]-(((((1+x))^m)-1)((((1+x))^n)-1)+(x^m)+(x^n))]=!=0&]

GraphData[{"CompleteBipartite",{2,3}},"DominationPolynomial"][x]

"CompleteBipartite"/.GraphData[{"CompleteBipartite",{2,3}},"NotationRules"]

CompleteTripartite k×m×n

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

DeleteCases[Block[{k,m,n},Expand@{{k,m,n}="CompleteTripartite"/.GraphData[#,"NotationRules"],
GraphData[#,"DominationPolynomial"][x],
2+x^k+x^m+x^n-(1+x)^k-(1+x)^m-(((1+x))^n)+(((1+x))^(k+m+n))}&/@GraphData["CompleteTripartite"]],{_,x_,x_}]

CompleteTripartite n×n×n

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

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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]

Expand[Subtract@@@Table[{2+3 (x^n)-3 (((1+x))^n)+(((1+x))^(3 n)),GraphData[{"CompleteTripartite",{n,n,n}},"DominationPolynomial"][x]},{n,9}]]

2+3 (x^n)-3 (((1+x))^n)+(((1+x))^(3 n))/.x->1//FullSimplify

CrossedPrism

(poly=Factor@Table[GraphData[{"CrossedPrism",n},"DominationPolynomial"][x],{n,k0=4,14,2}])//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]

Crown

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

coef=Factor/@FindPolynomialRecurrence[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]

rules=(#->With[{n="Crown"/.GraphData[#,"NotationRules"]},XXX])&/@GraphData["Crown",32;;]

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

Cycle

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

A212634

Table[Total[#2x^#&@@@Tally[Length/@FindDominatingSet[GraphData[{"Cycle",n}],∞,All]]],{n,3,6}]//Factor

p(1)=x, p(2) = 2x + x^2 , p(3) = 3x + 3x^2 + x^3 and p(n) = x*[p(n-1) + p(n-2) + p(n-3)]

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

FullSimplify[RSolve[{p[1,x]==x,p[2,x]==2x+x^2,p[3,x]==3x+3x^2+x^3 ,p[n,x]==x*(p[n-1,x]+p[n-2,x]+p[n-3,x])},p[n,x],n],n∈Integers&&n>3]

l={#,{0,With[{n="Cycle"/.GraphData[#,"NotationRules"]},LinearRecurrence[{x,x,x},{x,2x+x^2,3x+3x^2+x^3},n][[-1]]]}}&/@GraphData["Cycle"]

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

{"Cycle",2+#}&/@Flatten[Position[Expand[Table[GraphData[{"Cycle",n},"DominationPolynomial"][x],{n,3,20}]-LinearRecurrence[{x,x,x},{x,2x+x^2,3x+3x^2+x^3},{3,20}]],Except[0],1,Heads->False]]

CycleComplement

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

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

FindLinearRecurrence[Drop[poly,2]]

DiagonalIntersection

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

Dipyramid

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

gf=(z^3)FindGeneratingFunction[poly,z]

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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]

DorogovtsevGoltsevMendes

(poly=Factor@Table[GraphData[{"DorogovtsevGoltsevMendes",n},"DominationPolynomial"],{n,k0=0,7}]/.f_Function:>f[x])//Column

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

DoubleCone

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

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

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

Empty

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

(poly=Factor@Table[GraphData[{"Empty",n},"DominationPolynomial"][x],{n,k0=1,30}])

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

FibonacciCube

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

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

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

Fiveleaper n×n

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

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

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

Flower

(poly=Expand[Table[GraphData[{"Flower",n},"DominationPolynomial"],{n,k0=5,20}]/.f_Function:>f[x]])//Column

FindLinearRecurrence[DeleteMissing@poly]

FoldedCube

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

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

FindLinearRecurrence[poly]//Head//Timing

Gear

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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

LinearRecurrence[{x (5+2 x),-x (-1+6 x+6 (x^2)+(x^3)),(x^2) (-2-3 x+2 (x^2)+(x^3)),(x^3) (2+x) (-1+2 x),(x^3) (-1+2 x+2 (x^2)),(x^4) (1+x)},Take[poly,6],{2-k0,12}]

Select[GraphData["Gear"],Expand[GraphData[#,"DominationPolynomial"][x]-With[{n="Gear"/.GraphData[#,"NotationRules"]},LinearRecurrence[{x (5+2 x),-x (-1+6 x+6 (x^2)+(x^3)),(x^2) (-2-3 x+2 (x^2)+(x^3)),(x^3) (2+x) (-1+2 x),(x^3) (-1+2 x+2 (x^2)),(x^4) (1+x)},{x (1+3 x+(x^2)),(x^2) (7+10 x+5 (x^2)+(x^3)),(x^2) (3+19 x+32 (x^2)+21 (x^3)+7 (x^4)+(x^5)),(x^3) (2+x) (5+26 x+36 (x^2)+22 (x^3)+7 (x^4)+(x^5)),(x^4) (35+166 x+302 (x^2)+285 (x^3)+160 (x^4)+55 (x^5)+11 (x^6)+(x^7)),(x^4) (5+114 x+491 (x^2)+927 (x^3)+981 (x^4)+649 (x^5)+280 (x^6)+78 (x^7)+13 (x^8)+(x^9))},n][[-1]]]]=!=0&]

rules=(#->With[{n="Gear"/.GraphData[#,"NotationRules"]},Factor@LinearRecurrence[{x (5+2 x),-x (-1+6 x+6 (x^2)+(x^3)),(x^2) (-2-3 x+2 (x^2)+(x^3)),(x^3) (2+x) (-1+2 x),(x^3) (-1+2 x+2 (x^2)),(x^4) (1+x)},{x (1+3 x+(x^2)),(x^2) (7+10 x+5 (x^2)+(x^3)),(x^2) (3+19 x+32 (x^2)+21 (x^3)+7 (x^4)+(x^5)),(x^3) (2+x) (5+26 x+36 (x^2)+22 (x^3)+7 (x^4)+(x^5)),(x^4) (35+166 x+302 (x^2)+285 (x^3)+160 (x^4)+55 (x^5)+11 (x^6)+(x^7)),(x^4) (5+114 x+491 (x^2)+927 (x^3)+981 (x^4)+649 (x^5)+280 (x^6)+78 (x^7)+13 (x^8)+(x^9))},n][[-1]]])&/@GraphData["Gear",30;;]

Giraffe n×n

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

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

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

Goldberg

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

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

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

Grid m×n

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

Grid n×n

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

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

FindLinearRecurrence[DeleteMissing@poly]

FindGeneratingFunction[DeleteMissing@poly,z]

Grid k×m×n

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

Grid n×n×n

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

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

FindLinearRecurrence[DeleteMissing@poly]

FindGeneratingFunction[DeleteMissing@poly,z]

HalvedCube

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

rules=(#->With[{n="Book"/.GraphData[#,"NotationRules"]},-2 (x^n)+(x^2) (((1+x))^(2 n))+(((x (2+x)))^n) (1+2 x)])&/@GraphData["Book",32;;]

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

Hanoi

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

Helm

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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[#,"DominationPolynomial"][x]-With[{n="Helm"/.GraphData[#,"NotationRules"]},-(x^n)+(1+x) (((x (2+x)))^n)]]=!=0&]

Hypercube

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

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

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

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

Keller

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

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

rules=(#->With[{n="Barbell"/.GraphData[#,"NotationRules"]},(((-1+(((1+x))^n)))^2)])&/@GraphData["Barbell",32;;]

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

King n×n

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

Knight m×n

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

Knight n×n

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

Ladder

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

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

LinearRecurrence[{x (2+x),x (1+x),(x^2) (1+x),-(x^3),-(x^3)},Take[poly,5],6]

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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]

{"Ladder",#}&/@Flatten[Position[Expand[Table[GraphData[{"Ladder",n},"DominationPolynomial"][x],{n,20}]-LinearRecurrence[{x (2+x),x (1+x),(x^2) (1+x),-(x^3),-(x^3)},{x (2+x),(x^2) (6+4 x+(x^2)),(x^2) (3+16 x+15 (x^2)+6 (x^3)+(x^4)),(x^3) (12+48 x+52 (x^2)+28 (x^3)+8 (x^4)+(x^5)),(x^3) (2+47 x+148 (x^2)+178 (x^3)+116 (x^4)+45 (x^5)+10 (x^6)+(x^7))},20]],Except[0],1,Heads->False]]

LadderRung

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

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

FindLinearRecurrence[DeleteMissing@poly]

LucasCube

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

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

MengerSponge

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

MiddleLayer

(poly=Table[GraphData[{"MiddleLayer",n},"DominationPolynomial"],{n,5}]/.f_Function:>f[x])//Column

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

MoebiusLadder

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

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@Drop[poly,5]]//Head

Expand/@FindPolynomialRecurrence[DeleteMissing@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]]

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

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

Mycielski

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

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

Odd

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

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

Pan

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

coef=FindLinearRecurrence[DeleteMissing@poly]

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

recurrence=ToPolynomialRecurrence[p,x,n,coef]

Simplify[RSolve[{recurrence,Sequence@@Table[p[i+k0-1,x]==poly[[i]],{i,Length[coef]}]},p[n,x],n]]

gf=(x^k0)FindGeneratingFunction[poly,z]

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

Path

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

Table[Total[#2x^#&@@@Tally[Length/@FindDominatingSet[GraphData[{"Path",n}],∞,All]]],{n,5}]//Factor

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==x (Subscript[p, n-3])(x)+x (Subscript[p, n-2])(x)+x (Subscript[p, n-1])(x)]

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

LinearRecurrence[{x,x,x},{x,x (2+x),x (1+3 x+(x^2))},5]

{"Path",#}&/@Flatten[Position[Expand[Table[GraphData[{"Path",n},"DominationPolynomial"][x],{n,20}]-LinearRecurrence[{x,x,x},{x,x (2+x),x (1+3 x+(x^2))},20]],Except[0],1,Heads->False]]

PathComplement

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

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

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

Pell

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

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

PermutationStar

(poly=Table[GraphData[{"PermutationStar",n},"DominationPolynomial"],{n,5}]/.f_Function:>f[x])//Column

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

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

Prism

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

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

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

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

coef=Factor/@FindPolynomialRecurrence[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]

rules=(#->With[{n="Prism"/.GraphData[#,"NotationRules"]},XXX])&/@GraphData["Prism",;;10]

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

Queen n×n

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

Rook n×n

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

RookComplement n×n

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

SierpinskiCarpet

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

SierpinskiGasket

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

SierpinskiTetrahedron

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

StackedBook n×n

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

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

Star

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

Total[#2x^#&@@@Tally[Length/@FindDominatingSet[GraphData[{"Star",5}],∞,All]]]

Expand[(1+x)^4-1]

Total[#2x^#&@@@Tally[Length/@FindDominatingSet[GraphData["ClawGraph"],∞,All]]]

(x^3)+x (((1+x))^3)//Expand

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

l={#,{0,With[{n="Star"/.GraphData[#,"NotationRules"]},(x^(n-1))+x(((1+x))^(n-1))]}}&/@GraphData["Star"]

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

Sun

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==x (x+1) (Subscript[p, n-2])(x)+x (x+2) (Subscript[p, n-1])(x)]

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]

rules=(#->With[{n="Sun"/.GraphData[#,"NotationRules"]},Factor[Expand[(2^(-n)) ((((2 x+(x^2)-(Sqrt[x]) (Sqrt[4+x (8+x (4+x))])))^n)+(((2 x+(x^2)+(Sqrt[x]) (Sqrt[4+x (8+x (4+x))])))^n))]]])&/@GraphData["Sun",;;10]

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

Sunlet

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[%]

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["Sunlet"],Expand[GraphData[#,"DominationPolynomial"][x]-With[{n="Sunlet"/.GraphData[#,"NotationRules"]},(x (2+x))^n]]=!=0&]

Tetrahedral

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

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

TorusGrid n×n

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

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

Transposition

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

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

rules=(#->With[{n="Barbell"/.GraphData[#,"NotationRules"]},(((-1+(((1+x))^n)))^2)])&/@GraphData["Barbell",32;;]

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

Trapezohedron

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

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

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

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

Triangular

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

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

TriangularGrid

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

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[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]

rules=(#->With[{n="Barbell"/.GraphData[#,"NotationRules"]},(((-1+(((1+x))^n)))^2)])&/@GraphData["Barbell",32;;]

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

TriangularHoneycombAcuteKnight

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

rules=(#->With[{n="Book"/.GraphData[#,"NotationRules"]},-2 (x^n)+(x^2) (((1+x))^(2 n))+(((x (2+x)))^n) (1+2 x)])&/@GraphData["Book",32;;]

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

TriangularHoneycombBishop

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

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

TriangularHoneycombObtuseKnight

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

rules=(#->With[{n="Book"/.GraphData[#,"NotationRules"]},-2 (x^n)+(x^2) (((1+x))^(2 n))+(((x (2+x)))^n) (1+2 x)])&/@GraphData["Book",32;;]

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

TriangularHoneycombQueen

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

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

TriangularHoneycombRook

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

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

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

TriangularSnake

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

gf=(z^2) FindGeneratingFunction[DeleteMissing@poly,z]

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

Web

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==(((x+2))^2) (x^4) (Subscript[p, n-3])(x)+(x+2) (x^3) (Subscript[p, n-2])(x)+((x^2)+3 x+1) x (Subscript[p, n-1])(x)]

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]

Take[poly,3]

rules=(#->With[{n="Web"/.GraphData[#,"NotationRules"]},LinearRecurrence[{x (1+3 x+(x^2)),(x^3) (2+x),(x^4) (((2+x))^2)},{(x^3) (1+27 x+63 (x^2)+63 (x^3)+33 (x^4)+9 (x^5)+(x^6)),(x^4) (1+36 x+182 (x^2)+332 (x^3)+317 (x^4)+180 (x^5)+62 (x^6)+12 (x^7)+(x^8)),(x^5) (1+45 x+390 (x^2)+1160 (x^3)+1770 (x^4)+1633 (x^5)+980 (x^6)+390 (x^7)+100 (x^8)+15 (x^9)+(x^10))},n-k0+1][[-1]]])&/@GraphData["Web",32;;]

{"Web",2+#}&/@Flatten[Position[Expand[Table[GraphData[{"Web",n},"DominationPolynomial"][x],{n,3,20}]-(LinearRecurrence[{x (1+3 x+(x^2)),(x^3) (2+x),(x^4) (((2+x))^2)},{(x^3) (1+27 x+63 (x^2)+63 (x^3)+33 (x^4)+9 (x^5)+(x^6)),(x^4) (1+36 x+182 (x^2)+332 (x^3)+317 (x^4)+180 (x^5)+62 (x^6)+12 (x^7)+(x^8)),(x^5) (1+45 x+390 (x^2)+1160 (x^3)+1770 (x^4)+1633 (x^5)+980 (x^6)+390 (x^7)+100 (x^8)+15 (x^9)+(x^10))},{3,20}-2])],Except[0],1,Heads->False]]

Wheel

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

A212634

Table[Total[#2x^#&@@@Tally[Length/@FindDominatingSet[GraphData[{"Wheel",n}],∞,All]]],{n,4,6}]//Factor

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

p(1)=x, p(2) = 2x + x^2 , p(3) = 3x + 3x^2 + x^3 and p(n) = x*[p(n-1) + p(n-2) + p(n-3)]

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

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

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

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

TeXForm[(Subscript[p, n])(x)==-(x+1) (x^2) (Subscript[p, n-4])(x)-(2 x+3) (x^2) (Subscript[p, n-3])(x)-(x-1) (x+2) x (Subscript[p, n-2])(x)+(x+3) x (Subscript[p, n-1])(x)]

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

FullSimplify[SeriesCoefficient[%,{z,0,n}],n>3&&x∈Reals]

ByteCount/@{(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))),(1/(2 (Sqrt[x])))((((2^(-n)) ((-4-x+(Sqrt[x]) (Sqrt[4+x])) (((x+(Sqrt[x]) (Sqrt[4+x])))^n)+(((x-(Sqrt[x]) (Sqrt[4+x])))^n) (4+x+(Sqrt[x]) (Sqrt[4+x]))))/(Sqrt[4+x]))+(1/((1+x) (Sqrt[4+x (8+x (4+x))])))((2^(-n)) (((2 x+(x^2)+(Sqrt[x]) (Sqrt[4+x (8+x (4+x))])))^n) (4+8 x+4 (x^2)+(x^3)-2 (Sqrt[x]) (Sqrt[4+x (8+x (4+x))])-(x^(3/2)) (Sqrt[4+x (8+x (4+x))]))-(2^(-n)) (((2 x+(x^2)-(Sqrt[x]) (Sqrt[4+x (8+x (4+x))])))^n) (4+8 x+4 (x^2)+(x^3)+2 (Sqrt[x]) (Sqrt[4+x (8+x (4+x))])+(x^(3/2)) (Sqrt[4+x (8+x (4+x))]))))}

rules=(#->With[{n="Wheel"/.GraphData[#,"NotationRules"]},x(((1+x))^(n-1))+LinearRecurrence[{x,x,x},{x,2x+x^2,3x+3x^2+x^3},n-1][[-1]]])&/@GraphData["Wheel"]

{"Wheel",3+#}&/@Flatten[Position[Expand[Table[GraphData[{"Wheel",n},"DominationPolynomial"][x]-x(((1+x))^(n-1)),{n,4,20}]-(LinearRecurrence[{x,x,x},{x,2x+x^2,3x+3x^2+x^3},{4,20}-1])],Except[0],1,Heads->False]]

WheelComplement

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

gf=(z^k0)FindGeneratingFunction[DeleteMissing@poly,z]

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

FindLinearRecurrence[Drop[poly,2]]

WhiteBishop n×n

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

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

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

Zebra n×n

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

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

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