Visibility Polynomial

Author

Eric W. Weisstein
October 27, 2025

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

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

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

Sources

Tonny, K. B. and Shikhi, M.  On the Visibility Polynomial of Graphs.  2 Jul 2025.  https://arxiv.org/abs/2507.01851

Parametrized families

<<MathWorld`Graphs`

Alkane

Inferred for n > 6:

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

Length@DeleteMissing@poly

gf=z FindGeneratingFunction[DeleteMissing@poly,z]//Factor

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

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

AlternatingGroupGraph

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

Andasfai

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

Length@DeleteMissing@poly

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

Antiprism

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

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

poly={1+6 x+15 (x^2)+20 (x^3)+15 (x^4)+6 (x^5),1+8 x+28 (x^2)+56 (x^3)+60 (x^4)+24 (x^5),1+10 x+45 (x^2)+110 (x^3)+140 (x^4)+80 (x^5)+10 (x^6),1+12 x+66 (x^2)+208 (x^3)+345 (x^4)+240 (x^5)+40 (x^6),1+14 x+91 (x^2)+322 (x^3)+581 (x^4)+462 (x^5)+112 (x^6),1+16 x+120 (x^2)+512 (x^3)+1136 (x^4)+1088 (x^5)+272 (x^6),1+18 x+153 (x^2)+708 (x^3)+1656 (x^4)+1674 (x^5)+549 (x^6),1+20 x+190 (x^2)+1020 (x^3)+2825 (x^4)+3400 (x^5)+1140 (x^6),1+22 x+231 (x^2)+1320 (x^3)+3795 (x^4)+4642 (x^5)+1881 (x^6),1+24 x+276 (x^2)+1784 (x^3)+5916 (x^4)+8520 (x^5)+3592 (x^6),1+26 x+325 (x^2)+2210 (x^3)+7540 (x^4)+10816 (x^5)+5200 (x^6),1+28 x+378 (x^2)+2856 (x^3)+11025 (x^4)+18424 (x^5)+9352 (x^6),1+30 x+435 (x^2)+3430 (x^3)+13545 (x^4)+22290 (x^5)+12400 (x^6),1+32 x+496 (x^2)+4288 (x^3)+18880 (x^4)+35840 (x^5)+21248 (x^6),1+34 x+561 (x^2)+5032 (x^3)+22576 (x^4)+41922 (x^5)+26503 (x^6),1+36 x+630 (x^2)+6132 (x^3)+30321 (x^4)+64368 (x^5)+43596 (x^6),1+38 x+703 (x^2)+7068 (x^3)+35511 (x^4)+73454 (x^5)+52041 (x^6),1+40 x+780 (x^2)+8440 (x^3)+46300 (x^4)+108600 (x^5)+82640 (x^6),1+42 x+861 (x^2)+9590 (x^3)+53340 (x^4)+121632 (x^5)+95494 (x^6),1+44 x+946 (x^2)+11264 (x^3)+67881 (x^4)+174240 (x^5)+147048 (x^6),1+46 x+1035 (x^2)+12650 (x^3)+77165 (x^4)+192326 (x^5)+165784 (x^6),1+48 x+1128 (x^2)+14656 (x^3)+96240 (x^4)+268224 (x^5)+248464 (x^6),1+50 x+1225 (x^2)+16300 (x^3)+108200 (x^4)+292650 (x^5)+274825 (x^6),1+52 x+1326 (x^2)+18668 (x^3)+132665 (x^4)+398840 (x^5)+402116 (x^6)};

2+Length@DeleteMissing@poly

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

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

FindSequenceFunction[DeleteCases[Coefficient[poly,x,1],0],n-2]

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

gf3=(z^3)FindGeneratingFunction[DeleteCases[Coefficient[poly,x,3],0],z]

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

Coefficient[poly,x,3]

Table[(1/24) n (-17-18 n+26 (n^2)+3 (((-1))^n) (-5+2 n)),{n,3,20}]

gf4=FindGeneratingFunction[DeleteCases[Coefficient[poly,x,4],0],z,ValidationLength->2]

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

Table[(1/48) (3+n) (243+307 n+117 (n^2)+14 (n^3)-3 (((-1))^n) (1+3 n (3+n))),{n,3,20}]

FindGeneratingFunction[DeleteCases[Coefficient[poly,x,5],0],z,ValidationLength->2]//Head//Timing

FindGeneratingFunction[DeleteCases[Coefficient[poly,x,6],0],z,ValidationLength->2]//Head//Timing

Do[Print[{gn={"Antiprism",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Apollonian

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

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

Barbell

Inferred for n > 9:

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

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

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

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

Bishop n×n

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

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

BlackBishop n×n

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

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

Book

Inferred for n > 11:

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

FindLinearRecurrence[DeleteMissing@poly]

gf=z FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]

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

Bruhat

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

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

Cameron

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

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

Camel n×n

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

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

Cameron

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

Centipede

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

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

CocktailParty

Table[GraphData[{"CocktailParty",n},"VertexCutCount"],{n,10}]

Inferred for n > 8:

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

FindLinearRecurrence[poly]

gf=z FindGeneratingFunction[Most@DeleteMissing@poly,z]

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

Complete

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

poly=Table[GraphData[{"Complete",n},"VisibilityPolynomial"],{n,k0=1,kmax=30}]/.f_Function:>f[x]

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

Exponent[(1+x)^n,x,Max]

(1+x)^n/.x->1

Tonny, K. B. and Shikhi, M.  On the Visibility Polynomial of Graphs.  2 Jul 2025.  https://arxiv.org/abs/2507.01851

Do[Print[{gn={"Complete",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,6}]

Do[Print[Expand@{n,(((1+x))^n)}],{n,6}]

(((1+x))^n)/.x->1

Exponent[(((1+x))^n),x,Max]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["VisibilityPolynomial"]/.f_Function:>f[x]

Tonny, K. B. and Shikhi, M.  On the Visibility Polynomial of Graphs.  2 Jul 2025.  https://arxiv.org/abs/2507.01851

Actually true for n >= 2 AFAICT

sum[m_,n_,x_]:=1+Sum[Binomial[m+n,k](x^k),{k,m+1}]+Sum[(Binomial[m+n,k]-Binomial[n,k-m])(x^k),{k,m+2,n+1}]+Sum[(Binomial[m+n,k]-Binomial[n,k-m]-Binomial[m,k-n])(x^k),{k,n+2,m+n-2}]

sum[m,n,x]

FullSimplify[FunctionExpand[sum[m,n]],3<=m<=n&&(m|n)∈Integers]

DeleteCases[
Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"VisibilityPolynomial"]/.f_Function:>Expand[f[x]],
Expand@Piecewise[{{x+Max[m,n](x^2)+(((1+x))^(Max[m,n])),Min[m,n]==1}},sum[m,n,x]]
},{n,20},{m,n}],1],
{_,x_,x_}]

CompleteBipartite n×n

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

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

FindLinearRecurrence[poly]//Head//Timing

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

Expand[Subtract@@{(((1+x))^(2 n))-2 (((x (1+x)))^n)+(x^n) (2+2 n x+(x^n)),(((1+x))^2)}/.n->1]

Tonny, K. B. and Shikhi, M.  On the Visibility Polynomial of Graphs.  2 Jul 2025.  https://arxiv.org/abs/2507.01851

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

FunctionExpand[%]//FullSimplify

Expand[-2 (x^n) (((1+x))^n)+(((1+x))^(2 n))+(x^n) (2+2 n x+(x^n))/.n->1]//Factor

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

Piecewise[{{(1+x)^2,n==1}},(1+x)^(2 n)+x^n (2+2 n x+x^n)-2 x^n (1+x)^n]/.x->1

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

FullSimplify[Exponent[(1+x)^(2 n)+x^n (2+2 n x+x^n)-2 x^n (1+x)^n,x,Max],n>1]

Exponent[(1+x)^2,x,Max]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["VisibilityPolynomial"]/.f_Function:>f[x]

CompleteTripartite n×n×n

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

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

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

CrossedPrism

(poly=Table[GraphData[{"CrossedPrism",n},"VisibilityPolynomial"],{n,4,22,2}]/.f_Function:>f[x])//Column

FindLinearRecurrence[DeleteMissing@poly]

Crown

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

Length@DeleteMissing@poly

FindGeneratingFunction[Most@DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

CubeConnectedCycle

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

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

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

Cycle

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

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

coef=FindLinearRecurrence[poly]

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

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

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

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

Tonny, K. B. and Shikhi, M.  On the Visibility Polynomial of Graphs.  2 Jul 2025.  https://arxiv.org/abs/2507.01851

Do[Print[{gn={"Cycle",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,6}]

r3[n_?OddQ]:=((n((n^2)-1))/24)
r3[n_?EvenQ]:=(((n-2)n(n+8))/24)

FullSimplify[Piecewise[{{1+n x+Binomial[n,2] x^2+n (n^2-1)/24 x^3,Mod[n,2]==1},{1+n x+Binomial[n,2] x^2+(n-2) n (n+8)/24 x^3,Mod[n,2]==0}}]/.x->1
]

InputForm[%]

Do[Print[Expand@{n,1+n x+Binomial[n,2](x^2)+r3[n](x^3)}],{n,3,6}]

CycleComplement

Inferred for n > 18:

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

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

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

Subtract@@{(((1+x))^n)-(x^(-2+n)) (n+n x+(x^2)),(((1+2 x))^2) (1+x (2+3 x))}/.n->6//Expand

DiagonalIntersection

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

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

Dipyramid

Inferred for n > 15:

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

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

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

FindLinearRecurrence[Drop[Most@DeleteMissing@poly,4]]

DorogovtsevGoltsevMendes

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

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

DoubleCone

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

k0-1+Length@DeleteMissing@poly

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

Empty

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

poly=Table[GraphData[{"Empty",n},"VisibilityPolynomial"],{n,k0=1,30}]/.f_Function:>f[x]

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

1+n x/.x->1

FibonacciCube

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

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

Fiveleaper n×n

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

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

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

Flower

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

k0-1+Length@DeleteMissing@poly

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

FoldedCube

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

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

Gear

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

k0-1+Length@DeleteMissing@poly

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

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Do[Print[{gn={"Gear",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Giraffe n×n

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

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

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

Goldberg

(poly=Table[GraphData[{"Goldberg",n},"VisibilityPolynomial"],{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}}]["VisibilityPolynomial"]

Grid n×n

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

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

k0-1+Length@DeleteMissing@poly

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

FindGeneratingFunction[DeleteMissing@poly,x,ValidationLength->2]//Head//Timing

Grid k×m×n

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

Grid n×n×n

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

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

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

HalvedCube

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

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

Hanoi

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

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

Helm

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

k0-1+Length@DeleteMissing@poly

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

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Do[Print[{gn={"Helm",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Hypercube

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

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

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

Keller

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

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

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

King n×n

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

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

Knight m×n

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

Knight n×n

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

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

Ladder

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

Inferred for n > 6:

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

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

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

FindLinearRecurrence[DeleteMissing@poly]

Factor[1+2 n x+n (-1+2 n) (x^2)+(-1+n) (n^2) (x^3)+(1/6) (-2+n) (-1+n) (-3-n+(n^2)) (x^4)/.x->1]

LadderRung

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

gf=z FindGeneratingFunction[DeleteMissing@Take[poly,5],z]

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

FindLinearRecurrence[DeleteMissing@poly]

LucasCube

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

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

MengerSponge

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

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

MiddleLayer

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

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

MoebiusLadder

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

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

k0-1+Length@DeleteMissing@poly

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

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Do[Print[{gn={"MoebiusLadder",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Mycielski

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

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

k0-1+Length@DeleteMissing@poly

Odd

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

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

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

Pan

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

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

FindLinearRecurrence[DeleteMissing@poly]

gf=(z^3)FindGeneratingFunction[DeleteCases[Coefficient[poly,x,3],0],z]

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

Table[1+(n+1)x+Binomial[n+1,2](x^2)+(1/48) (-18-29 n+18 (n^2)+2 (n^3)+3 (((-1))^n) (2+n) (-5+2 n))(x^3),{n,3,20}]-poly

Path

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

Tonny, K. B. and Shikhi, M.  On the Visibility Polynomial of Graphs.  2 Jul 2025.  https://arxiv.org/abs/2507.01851

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

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

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

PathComplement

Inferred for n > 17:

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

FindLinearRecurrence[DeleteMissing@Drop[poly,4]]

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

Pell

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

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

PermutationStar

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

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

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

PlummerToft

Inferred for n > 13:

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

FindLinearRecurrence[DeleteMissing@Drop[poly,2]]

gf=z FindGeneratingFunction[DeleteMissing@poly,z]

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

Prism

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

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

k0-1+Length@DeleteMissing@poly

poly={1+6 x+15 (x^2)+20 (x^3)+12 (x^4),1+8 x+28 (x^2)+56 (x^3)+64 (x^4)+24 (x^5),1+10 x+45 (x^2)+110 (x^3)+115 (x^4)+30 (x^5),1+12 x+66 (x^2)+208 (x^3)+351 (x^4)+252 (x^5)+2 (x^6),1+14 x+91 (x^2)+322 (x^3)+504 (x^4)+280 (x^5)+35 (x^6),1+16 x+120 (x^2)+512 (x^3)+1144 (x^4)+1136 (x^5)+224 (x^6),1+18 x+153 (x^2)+708 (x^3)+1485 (x^4)+1188 (x^5)+261 (x^6),1+20 x+190 (x^2)+1020 (x^3)+2835 (x^4)+3540 (x^5)+1200 (x^6),1+22 x+231 (x^2)+1320 (x^3)+3476 (x^4)+3564 (x^5)+1034 (x^6),1+24 x+276 (x^2)+1784 (x^3)+5928 (x^4)+8832 (x^5)+3904 (x^6),1+26 x+325 (x^2)+2210 (x^3)+7007 (x^4)+8710 (x^5)+3146 (x^6),1+28 x+378 (x^2)+2856 (x^3)+11039 (x^4)+19012 (x^5)+10136 (x^6),1+30 x+435 (x^2)+3430 (x^3)+12720 (x^4)+18540 (x^5)+8065 (x^6),1+32 x+496 (x^2)+4288 (x^3)+18896 (x^4)+36832 (x^5)+22784 (x^6),1+34 x+561 (x^2)+5032 (x^3)+21369 (x^4)+35700 (x^5)+18241 (x^6),1+36 x+630 (x^2)+6132 (x^3)+30339 (x^4)+65916 (x^5)+46224 (x^6),1+38 x+703 (x^2)+7068 (x^3)+33820 (x^4)+63688 (x^5)+37468 (x^6),1+40 x+780 (x^2)+8440 (x^3)+46320 (x^4)+110880 (x^5)+86760 (x^6),1+42 x+861 (x^2)+9590 (x^3)+51051 (x^4)+106974 (x^5)+71302 (x^6),1+44 x+946 (x^2)+11264 (x^3)+67903 (x^4)+177452 (x^5)+153120 (x^6),1+46 x+1035 (x^2)+12650 (x^3)+74152 (x^4)+171120 (x^5)+127535 (x^6),1+48 x+1128 (x^2)+14656 (x^3)+96264 (x^4)+272592 (x^5)+257008 (x^6),1+50 x+1225 (x^2)+16300 (x^3)+104325 (x^4)+262900 (x^5)+216725 (x^6),1+52 x+1326 (x^2)+18668 (x^3)+132691 (x^4)+404612 (x^5)+413712 (x^6)};

Coefficient[poly,x,1]/2

3-1+Length[poly]

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

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

gf=FindGeneratingFunction[DeleteMissing@poly[[1;;;;2]],z,ValidationLength->2]

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

FindGeneratingFunction[DeleteMissing@poly[[2;;;;2]],z,ValidationLength->2]//Head//Timing

gf3=(z^3)FindGeneratingFunction[DeleteCases[Coefficient[poly,x,3],0],z]

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

gf4=(z^3)FindGeneratingFunction[DeleteCases[Coefficient[poly,x,4],0],z,ValidationLength->2]

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

FindGeneratingFunction[DeleteCases[Coefficient[poly,x,5],0],z,ValidationLength->2]//Head//Timing

FindGeneratingFunction[DeleteCases[Coefficient[poly,x,6],0],z,ValidationLength->2]//Head//Timing

Do[Print[{gn={"Prism",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Queen n×n

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

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

Rook n×n

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

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

RookComplement n×n

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

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

SierpinskiCarpet

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

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

SierpinskiGasket

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

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

SierpinskiTetrahedron

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

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

StackedBook n×n

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

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

Star

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

(poly=Table[GraphData[{"Star",n},"VisibilityPolynomial"],{n,k0=1,kmax=25}]/.f_Function:>Expand[f[x]])//Column

FindLinearRecurrence[DeleteMissing@poly]

gf=z FindGeneratingFunction[poly,z]

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

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

Tonny, K. B. and Shikhi, M.  On the Visibility Polynomial of Graphs.  2 Jul 2025.  https://arxiv.org/abs/2507.01851

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

bug(465245): Exponent[x + (n - 1) x^2 + (1 + x)^(n - 1), x, Max] gives expression that is wrong for n == 1

Exponent[x+(n-1)(x^2)+(((1+x))^(n-1)),x,Max]

%/.n->1

Exponent[x+(n-1)(x^2)+(((1+x))^(n-1))/.n->1,x,Max]

Do[Print[{gn={"Star",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,6}]

Do[Print[Expand@{n,x+(n-1) (x^2)+(((1+x))^(n-1))}],{n,6}]

Sun

Inferred for n > 13:

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

2+Length@DeleteMissing@poly

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

Take[poly,Length@coef]

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],n∈Integers]

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

Do[Print[{gn={"Sun",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Sunlet

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

k0-1+Length@DeleteMissing@poly

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

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

Do[Print[{gn={"Sunlet",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Tetrahedral

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

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

TorusGrid n×n

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

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

Transposition

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

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

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

Trapezohedron

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

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

k0-1+Length@DeleteMissing@poly

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

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

Do[Print[{gn={"Trapezohedron",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Triangular

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

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

TriangularGrid

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

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

TriangularHoneycombAcuteKnight

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

k0-1+Length@DeleteMissing@poly

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

TriangularHoneycombBishop

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

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

TriangularHoneycombObtuseKnight

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

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

TriangularHoneycombQueen

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

k0-1+Length@DeleteMissing@poly

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

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

TriangularHoneycombRook

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

FindLinearRecurrence[DeleteMissing@poly]

gf=z FindGeneratingFunction[poly,z]

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

TriangularSnake

Inferred for n == 19:

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

gf=FindGeneratingFunction[DeleteMissing@poly,z]

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

%/.n->(n-1)/2//FullSimplify

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

Web

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

k0-1+Length@DeleteMissing@poly

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

FindGeneratingFunction[DeleteMissing@poly,z,ValidationLength->2]//Head//Timing

Do[Print[{gn={"Web",n},VisibilityPolynomial[GraphData[gn],x]//Timing}],{n,3,20}]

Wheel

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

Inferred for n > 17:

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

FindLinearRecurrence[DeleteMissing@Drop[poly,4]]

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

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

Table[x+(-1+n) (x^2)+2 (-1+n) (x^3)+(((1+x))^(-1+n))-GraphData[{"Wheel",n},"VisibilityPolynomial"][x],{n,4,15}]//Expand//Column

WheelComplement

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

FindGeneratingFunction[Most@DeleteMissing@Take[poly,17],z]//Head//Timing

WhiteBishop n×n

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

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

Zebra n×n

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

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