Rank Polynomial

Author

Eric W. Weisstein
November 14, 2008

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

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

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

Examples

Cyclic

TuttePolynomial[Graph["C12"],{x,y}]

(Subscript[K, 3,3])

RankPolynomial[Graph["K3,3"],{x,y}]//TraditionalForm

RankMatrix[Graph["K3,3"]]//TraditionalForm

Factor[RankPolynomial[Graph["K3,3"],{x,x}]]

M[Graph["K3,3"]]

Petersen

TuttePolynomial[Graph["PetersenGraph"],{x,y}]//TraditionalForm

TutteMatrix[Graph["PetersenGraph"]]//TraditionalForm

Special Cases

Andrasfai

(l=Table[GraphData[{"Andrasfai",n},"RankPolynomial"][x,y],{n,1,4}]//Factor)//Column//TraditionalForm

FindLinearRecurrence[l]

Antiprism

l=Append[Table[GraphData[{"Antiprism",n},"RankPolynomial"][x,y],{n,3,6}],1+28 x+378 (x^2)+3262 (x^3)+20111 (x^4)+93758 (x^5)+341117 (x^6)+984916 (x^7)+2270786 (x^8)+4166302 (x^9)+5991615 (x^10)+6516832 (x^11)+4918795 (x^12)+1989806 (x^13)+14 (x^2) y+364 (x^3) y+4508 (x^4) y+35196 (x^5) y+193146 (x^6) y+785967 (x^7) y+2436742 (x^8) y+5817259 (x^9) y+10658620 (x^10) y+14643860 (x^11) y+14019278 (x^12) y+7274405 (x^13) y+14 (x^3) (y^2)+427 (x^4) (y^2)+5964 (x^5) (y^2)+50876 (x^6) (y^2)+296688 (x^7) (y^2)+1249829 (x^8) (y^2)+3910004 (x^9) (y^2)+9183923 (x^10) (y^2)+16077572 (x^11) (y^2)+19804975 (x^12) (y^2)+13415584 (x^13) (y^2)+14 (x^4) (y^3)+476 (x^5) (y^3)+7154 (x^6) (y^3)+63896 (x^7) (y^3)+380716 (x^8) (y^3)+1602160 (x^9) (y^3)+4917836 (x^10) (y^3)+11184530 (x^11) (y^3)+18167632 (x^12) (y^3)+16464483 (x^13) (y^3)+14 (x^5) (y^4)+511 (x^6) (y^4)+7994 (x^7) (y^4)+72485 (x^8) (y^4)+429226 (x^9) (y^4)+1776432 (x^10) (y^4)+5407276 (x^11) (y^4)+11995802 (x^12) (y^4)+14992796 (x^13) (y^4)+14 (x^6) (y^5)+532 (x^7) (y^5)+8428 (x^8) (y^5)+75719 (x^9) (y^5)+443212 (x^10) (y^5)+1885541 (x^11) (y^5)+5995262 (x^12) (y^5)+10709944 (x^13) (y^5)+14 (x^7) (y^6)+539 (x^8) (y^6)+8442 (x^9) (y^6)+75397 (x^10) (y^6)+477806 (x^11) (y^6)+2326128 (x^12) (y^6)+6189064 (x^13) (y^6)+14 (x^8) (y^7)+532 (x^9) (y^7)+8302 (x^10) (y^7)+86513 (x^11) (y^7)+707154 (x^12) (y^7)+2939727 (x^13) (y^7)+14 (x^9) (y^8)+525 (x^10) (y^8)+10668 (x^11) (y^8)+167573 (x^12) (y^8)+1153758 (x^13) (y^8)+14 (x^10) (y^9)+805 (x^11) (y^9)+30254 (x^12) (y^9)+372785 (x^13) (y^9)+28 (x^11) (y^10)+3955 (x^12) (y^10)+97944 (x^13) (y^10)+336 (x^12) (y^11)+20461 (x^13) (y^11)+14 (x^12) (y^12)+3276 (x^13) (y^12)+378 (x^13) (y^13)+28 (x^13) (y^14)+(x^13) (y^15)]

FindLinearRecurrence[l]

FindPolynomialRecurrence[l,3]

Apollonian

l=Table[GraphData[{"Apollonian",n},"RankPolynomial"][x,y],{n,2}]

Factor/@FindLinearRecurrence[l]

Barbell

l=Table[GraphData[{"Barbell",n},"RankPolynomial"][x,y],{n,3,5}]

Factor/@FindLinearRecurrence[l]

(l=Table[Sqrt[GraphData[{"Barbell",n},"RankPolynomial"][x,y]/(x+1)]//PowerExpand,{n,3,5}]//Factor)

FindLinearRecurrence[l]

Book

(l=Table[GraphData[{"Book",n},"RankPolynomial"][x,y],{n,3,20}]//Factor)

Factor/@FindLinearRecurrence[l]

p[n]==(2+6 x+6 (x^2)+(x^2) y)p[n-1]-(1+3 x+3 (x^2)) (1+3 x+3 (x^2)+(x^2) y)p[n-2]//TraditionalForm

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

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

rules=Table[GraphData[{"Book",n},"#"]->(((((1+3 x (1+x)))^n) (-x+y)+x (1+y) (((1+x (3+x (3+y))))^n))/y),{n,3,20}]

Centipede

l=Table[GraphData[{"Centipede",n},"RankPolynomial"][x,y],{n,10}]

eqns=Table[l[[i]]==a l[[i-1]],{i,3,Length[l]}];

Factor/@Solve[eqns,{a}]

rules=Table[GraphData[{"Centipede",n},"#"]->(((x+1))^(2n-1)),{n,10}]

CocktailParty

l=Table[GraphData[{"CocktailParty",n},"RankPolynomial"][x,y],{n,4}]

Factor/@FindLinearRecurrence[l]

Complete

l=Table[GraphData[{"Complete",n},"RankPolynomial"][x,y],{n,8}]

Factor/@FindLinearRecurrence[l]

CoefficientList[GraphData[{"Complete",3},"RankPolynomial"][x,y],{x,y}]//TraditionalForm

CoefficientList[GraphData[{"Complete",4},"RankPolynomial"][x,y],{x,y}]//TraditionalForm

CoefficientList[GraphData[{"Complete",6},"RankPolynomial"][x,y],{x,y}]//TraditionalForm

FindSequenceFunction[Reverse@#,n]&/@DeleteCases[CoefficientList[GraphData[{"Complete",6},"RankPolynomial"][x,y],{x,y}],0,{2}]

CoefficientList[GraphData[{"Complete",7},"RankPolynomial"][x,y],{x,y}]//TraditionalForm

FindSequenceFunction[Reverse@#,n]&/@DeleteCases[CoefficientList[GraphData[{"Complete",7},"RankPolynomial"][x,y],{x,y}],0,{2}]

CompleteBipartite

l=Table[GraphData[{"CompleteBipartite",{n,n}},"RankPolynomial"][x,y],{n,5}]

FindLinearRecurrence[l]

eqns=Table[l[[i]]==a l[[i-1]]+b l[[i-2]],{i,3,Length[l]}];

Solve[eqns,{a,b}]

CrossedPrism

(l=Table[GraphData[{"CrossedPrism",n},"RankPolynomial"][x,y],{n,4,8,2}]//Factor)

Factor/@FindLinearRecurrence[l]

Crown

l=Table[GraphData[{"Crown",n},"RankPolynomial"][x,y],{n,3,6}]//Factor

Factor/@FindLinearRecurrence[l]

CubeConnectedCycle

Table[GraphData[{"CubeConnectedCycle",n},"RankPolynomial"][x,y],{n,3,3}]

Cycle

l=Table[GraphData[{"Cycle",n},"RankPolynomial"][x,y],{n,3,20}]

Factor/@FindLinearRecurrence[l]

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

Table[(x^(n-1 ))y+Sum[Binomial[n,k](x^k),{k,0,n-1}],{n,3,6}]//Column//TraditionalForm

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

TraditionalForm[%]

Table[GraphData[{"Cycle",n},"RankPolynomial"][x,y],{n,3,20}]-Table[(((1+x))^n)+(x^(-1+n)) (-x+y),{n,3,20}]//Expand

FoldedCube

l=Table[GraphData[{"FoldedCube",n},"RankPolynomial"][x,y],{n,2,4}]//Factor

Factor/@FindLinearRecurrence[l]

Gear

(l=Table[GraphData[{"Gear",n},"RankPolynomial"][x,y],{n,3,10}]//Factor)

Factor/@FindLinearRecurrence[l]

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

Refine[%4,n∈Integers&&n>0]//Simplify

TraditionalForm[(1/x)(2^(-n)) (-(2^(1+n)) (x^(1+2 n))+(2^n) (x^(2 n)) y+x (((1+3 x+(x^2) (4+y)-(Sqrt[1+6 x+(x^2) (13-2 y)-2 (x^3) (-8+y)+(x^4) (12+4 y+(y^2))])))^n)+x (((1+3 x+(x^2) (4+y)+(Sqrt[1+6 x+(x^2) (13-2 y)-2 (x^3) (-8+y)+(x^4) (12+4 y+(y^2))])))^n))/.(Sqrt[1+6 x+(x^2) (13-2 y)-2 (x^3) (-8+y)+(x^4) (12+4 y+(y^2))])->v]

Table[GraphData[{"Gear",n},"RankPolynomial"][x,y],{n,3,8}]-Table[(1/x)(2^(-n)) (-(2^(1+n)) (x^(1+2 n))+(2^n) (x^(2 n)) y+x (((1+3 x+(x^2) (4+y)-(Sqrt[1+6 x+(x^2) (13-2 y)-2 (x^3) (-8+y)+(x^4) (12+4 y+(y^2))])))^n)+x (((1+3 x+(x^2) (4+y)+(Sqrt[1+6 x+(x^2) (13-2 y)-2 (x^3) (-8+y)+(x^4) (12+4 y+(y^2))])))^n)),{n,3,8}]//Expand

rules=Table[GraphData[{"Gear",n},"#"]->Expand[(1/x)(2^(-n)) (-(2^(1+n)) (x^(1+2 n))+(2^n) (x^(2 n)) y+x (((1+3 x+(x^2) (4+y)-(Sqrt[1+6 x+(x^2) (13-2 y)-2 (x^3) (-8+y)+(x^4) (12+4 y+(y^2))])))^n)+x (((1+3 x+(x^2) (4+y)+(Sqrt[1+6 x+(x^2) (13-2 y)-2 (x^3) (-8+y)+(x^4) (12+4 y+(y^2))])))^n))],{n,3,20}]

2-Grid

(l=Table[GraphData[{"Grid",{n,n}},"RankPolynomial"][x,y],{n,4}]//Factor)

Factor/@FindLinearRecurrence[l]

3-Grid

l=Table[GraphData[{"Grid",{n,n,n}},"RankPolynomial"][x,y],{n,2}]//Factor

3-Grid

l=Table[GraphData[{"Grid",{n,n,n}},"RankPolynomial"][x,y],{n,2}]//Factor

HalvedCube

l=Table[GraphData[{"HalvedCube",n},"RankPolynomial"][x,y],{n,4}]//Factor

Factor/@FindLinearRecurrence[l]

Hanoi

l=Table[GraphData[{"Hanoi",n},"RankPolynomial"][x,y],{n,2}]//Factor

Helm

(l=Table[GraphData[{"Helm",n},"RankPolynomial"][x,y],{n,3,9}]//Factor)

Factor/@FindLinearRecurrence[l]

p(n)==(x^2) (((x+1))^4) (y+1) p(n-3)-x (2 x+1) (((x+1))^2) (y+2) p(n-2)+(x+1) p(n-1) (x y+4 x+1)

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

FullSimplify[{{p[n]->-(1/x)(2^(-n)) ((2^(1+n)) x (((x+(x^2)))^n)-(2^n) (((x+(x^2)))^n) y-x (((1+4 x+3 (x^2)+x y+(x^2) y-(1+x) (Sqrt[1+2 x+5 (x^2)-2 x y+2 (x^2) y+(x^2) (y^2)])))^n)-x (((1+4 x+3 (x^2)+x y+(x^2) y+(1+x) (Sqrt[1+2 x+5 (x^2)-2 x y+2 (x^2) y+(x^2) (y^2)])))^n))}},n∈Integers&&n>0]

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

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

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

Hypercube

l=Table[GraphData[{"Hypercube",n},"RankPolynomial"][x,y],{n,3}]//Factor

Factor/@FindLinearRecurrence[l]

KingsTour

l=Table[GraphData[{"KingsTour",{n,n}},"RankPolynomial"][x,y],{n,3,3}]//Factor

Ladder

l=Table[GraphData[{"Ladder",n},"RankPolynomial"][x,y],{n,9}]//Factor

Factor/@FindLinearRecurrence[l]

l-RecurrenceTable[{p[n]==(1+3 x+4 (x^2)+(x^2) y)p[n-1]+(-(x^2) (1+2 x+(x^2)) (1+y))p[n-2],p[1]==l[[1]],p[2]==l[[2]]},p,{n,9}]//Expand

rules=Thread[Table[GraphData[{"Ladder",n},"#"],{n,20}]->RecurrenceTable[{p[n]==(1+3 x+4 (x^2)+(x^2) y)p[n-1]+(-(x^2) (1+2 x+(x^2)) (1+y))p[n-2],p[1]==l[[1]],p[2]==l[[2]]},p,{n,20}]//Factor]

p(n)==p(n-1) ((x^2) y+4 (x^2)+3 x+1)-p(n-2) ((x^2) ((x^2)+2 x+1) (y+1))

FullSimplify[RSolve[{p[n]==(1+3 x+4 (x^2)+(x^2) y)p[n-1]+(-(x^2) (1+2 x+(x^2)) (1+y))p[n-2],p[1]==l[[1]],p[2]==l[[2]]},p[n],n],(x|y)∈Reals&&n>0&&n∈Integers]

FullSimplify[((2^(-1-n)) (-(1+x (3+x (2+2 x-y))) (((1+x (3+x (4+y))-(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))])))^n)+(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))]) (((1+x (3+x (4+y))-(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))])))^n)+(1+x (3+x (2+2 x-y))) (((1+x (3+x (4+y))+(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))])))^n)+(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))]) (((1+x (3+x (4+y))+(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))])))^n)))/((((1+x))^2) (Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))]))/.{(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))])->s,1/(Sqrt[1+x (6+x (13-2 x (-8+y)-2 y+(x^2) (12+y (4+y))))])->1/s},n∈Integers&&n>0]//TraditionalForm

Table[GraphData[{"Ladder",n},"RankPolynomial"][x,y],{n,4}]//Factor//Column//TraditionalForm

Table[CoefficientList[GraphData[{"Ladder",n},"RankPolynomial"][x,y],{x,y}],{n,5}]//TraditionalForm

LadderRung

l=Table[GraphData[{"LadderRung",n},"RankPolynomial"][x,y],{n,20}]

Factor/@FindLinearRecurrence[l]

Lattice

Table[GraphData[{"Lattice",{n,n}},"RankPolynomial"][x,y],{n,2,3}]//Factor

MoebiusLadder

l=Table[GraphData[{"MoebiusLadder",n},"RankPolynomial"][x,y],{n,3,8}]

{{"MoebiusLadder",9},{92818.90081999992`,1+27 x+351 (x^2)+2925 (x^3)+17541 (x^4)+80523 (x^5)+293724 (x^6)+871920 (x^7)+2138868 (x^8)+4375812 (x^9)+7498125 (x^10)+10758159 (x^11)+12857625 (x^12)+12654495 (x^13)+10039518 (x^14)+6162102 (x^15)+2673081 (x^16)+632043 (x^17)+9 (x^3) y+207 (x^4) y+2286 (x^5) y+16101 (x^6) y+81000 (x^7) y+308772 (x^8) y+922950 (x^9) y+2207169 (x^10) y+4267959 (x^11) y+6694245 (x^12) y+8483382 (x^13) y+8573619 (x^14) y+6700950 (x^15) y+3742074 (x^16) y+1160079 (x^17) y+9 (x^5) (y^2)+207 (x^6) (y^2)+2241 (x^7) (y^2)+15201 (x^8) (y^2)+72369 (x^9) (y^2)+256275 (x^10) (y^2)+697131 (x^11) (y^2)+1482183 (x^12) (y^2)+2481588 (x^13) (y^2)+3269304 (x^14) (y^2)+3336498 (x^15) (y^2)+2473470 (x^16) (y^2)+1039977 (x^17) (y^2)+9 (x^7) (y^3)+198 (x^8) (y^3)+2001 (x^9) (y^3)+12420 (x^10) (y^3)+53037 (x^11) (y^3)+164940 (x^12) (y^3)+385875 (x^13) (y^3)+693846 (x^14) (y^3)+967680 (x^15) (y^3)+1000836 (x^16) (y^3)+598230 (x^17) (y^3)+9 (x^9) (y^4)+180 (x^10) (y^4)+1611 (x^11) (y^4)+8676 (x^12) (y^4)+31671 (x^13) (y^4)+84444 (x^14) (y^4)+173835 (x^15) (y^4)+270666 (x^16) (y^4)+244662 (x^17) (y^4)+9 (x^11) (y^5)+153 (x^12) (y^5)+1152 (x^13) (y^5)+5418 (x^14) (y^5)+18999 (x^15) (y^5)+50211 (x^16) (y^5)+74430 (x^17) (y^5)+9 (x^13) (y^6)+135 (x^14) (y^6)+1137 (x^15) (y^6)+6273 (x^16) (y^6)+17064 (x^17) (y^6)+27 (x^15) (y^7)+486 (x^16) (y^7)+2907 (x^17) (y^7)+18 (x^16) (y^8)+351 (x^17) (y^8)+27 (x^17) (y^9)+(x^17) (y^10)}}[[2,2]]

l2=Append[l,1+27 x+351 (x^2)+2925 (x^3)+17541 (x^4)+80523 (x^5)+293724 (x^6)+871920 (x^7)+2138868 (x^8)+4375812 (x^9)+7498125 (x^10)+10758159 (x^11)+12857625 (x^12)+12654495 (x^13)+10039518 (x^14)+6162102 (x^15)+2673081 (x^16)+632043 (x^17)+9 (x^3) y+207 (x^4) y+2286 (x^5) y+16101 (x^6) y+81000 (x^7) y+308772 (x^8) y+922950 (x^9) y+2207169 (x^10) y+4267959 (x^11) y+6694245 (x^12) y+8483382 (x^13) y+8573619 (x^14) y+6700950 (x^15) y+3742074 (x^16) y+1160079 (x^17) y+9 (x^5) (y^2)+207 (x^6) (y^2)+2241 (x^7) (y^2)+15201 (x^8) (y^2)+72369 (x^9) (y^2)+256275 (x^10) (y^2)+697131 (x^11) (y^2)+1482183 (x^12) (y^2)+2481588 (x^13) (y^2)+3269304 (x^14) (y^2)+3336498 (x^15) (y^2)+2473470 (x^16) (y^2)+1039977 (x^17) (y^2)+9 (x^7) (y^3)+198 (x^8) (y^3)+2001 (x^9) (y^3)+12420 (x^10) (y^3)+53037 (x^11) (y^3)+164940 (x^12) (y^3)+385875 (x^13) (y^3)+693846 (x^14) (y^3)+967680 (x^15) (y^3)+1000836 (x^16) (y^3)+598230 (x^17) (y^3)+9 (x^9) (y^4)+180 (x^10) (y^4)+1611 (x^11) (y^4)+8676 (x^12) (y^4)+31671 (x^13) (y^4)+84444 (x^14) (y^4)+173835 (x^15) (y^4)+270666 (x^16) (y^4)+244662 (x^17) (y^4)+9 (x^11) (y^5)+153 (x^12) (y^5)+1152 (x^13) (y^5)+5418 (x^14) (y^5)+18999 (x^15) (y^5)+50211 (x^16) (y^5)+74430 (x^17) (y^5)+9 (x^13) (y^6)+135 (x^14) (y^6)+1137 (x^15) (y^6)+6273 (x^16) (y^6)+17064 (x^17) (y^6)+27 (x^15) (y^7)+486 (x^16) (y^7)+2907 (x^17) (y^7)+18 (x^16) (y^8)+351 (x^17) (y^8)+27 (x^17) (y^9)+(x^17) (y^10)]

Factor/@FindLinearRecurrence[l]

Factor/@FindPolynomialRecurrence[l,2]

Mycielski

l=Table[GraphData[{"Mycielski",n},"RankPolynomial"][x,y],{n,3,4}]//Factor

Odd

l=Table[GraphData[{"Odd",n},"RankPolynomial"][x,y],{n,2,3}]//Factor

Pan

l=Table[GraphData[{"Pan",n},"RankPolynomial"][x,y],{n,3,7}]

Factor/@FindLinearRecurrence[l]

Table[GraphData[{"Pan",n},"RankPolynomial"][x,y],{n,3,7}]-(x+1)Table[(((1+x))^n)+(x^(-1+n)) (-x+y),{n,3,7}]//Expand

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

TraditionalForm[%]

Path

l=Table[GraphData[{"Path",n},"RankPolynomial"][x,y],{n,20}]//Factor

Factor/@FindLinearRecurrence[l]

PermutationStar

l=Table[GraphData[{"PermutationStar",n},"RankPolynomial"][x,y],{n,3}]//Factor

Factor/@FindLinearRecurrence[l]

Prism

l=AppendTo[Table[GraphData[{"Prism",n},"RankPolynomial"][x,y],{n,3,8}],
1+27 x+351 (x^2)+2925 (x^3)+17541 (x^4)+80523 (x^5)+293724 (x^6)+871920 (x^7)+2138868 (x^8)+4375810 (x^9)+7498107 (x^10)+10758087 (x^11)+12857457 (x^12)+12654243 (x^13)+10039266 (x^14)+6161934 (x^15)+2673009 (x^16)+632025 (x^17)+9 (x^3) y+207 (x^4) y+2286 (x^5) y+16101 (x^6) y+81000 (x^7) y+308774 (x^8) y+922968 (x^9) y+2207241 (x^10) y+4268127 (x^11) y+6694497 (x^12) y+8483634 (x^13) y+8573787 (x^14) y+6701022 (x^15) y+3742092 (x^16) y+1160078 (x^17) y+9 (x^5) (y^2)+207 (x^6) (y^2)+2241 (x^7) (y^2)+15201 (x^8) (y^2)+72369 (x^9) (y^2)+256275 (x^10) (y^2)+697131 (x^11) (y^2)+1482183 (x^12) (y^2)+2481588 (x^13) (y^2)+3269304 (x^14) (y^2)+3336498 (x^15) (y^2)+2473471 (x^16) (y^2)+1039977 (x^17) (y^2)+9 (x^7) (y^3)+198 (x^8) (y^3)+2001 (x^9) (y^3)+12420 (x^10) (y^3)+53037 (x^11) (y^3)+164940 (x^12) (y^3)+385875 (x^13) (y^3)+693846 (x^14) (y^3)+967680 (x^15) (y^3)+1000836 (x^16) (y^3)+598230 (x^17) (y^3)+9 (x^9) (y^4)+180 (x^10) (y^4)+1611 (x^11) (y^4)+8676 (x^12) (y^4)+31671 (x^13) (y^4)+84444 (x^14) (y^4)+173835 (x^15) (y^4)+270666 (x^16) (y^4)+244662 (x^17) (y^4)+9 (x^11) (y^5)+153 (x^12) (y^5)+1152 (x^13) (y^5)+5418 (x^14) (y^5)+18999 (x^15) (y^5)+50211 (x^16) (y^5)+74430 (x^17) (y^5)+9 (x^13) (y^6)+135 (x^14) (y^6)+1137 (x^15) (y^6)+6273 (x^16) (y^6)+17064 (x^17) (y^6)+27 (x^15) (y^7)+486 (x^16) (y^7)+2907 (x^17) (y^7)+18 (x^16) (y^8)+351 (x^17) (y^8)+27 (x^17) (y^9)+(x^17) (y^10)]

Factor/@FindPolynomialRecurrence[l,4]

Factor/@FindLinearRecurrence[l]

Sierpinski

Table[GraphData[{"Sierpinski",n},"RankPolynomial"][x,y],{n,2}]//Factor

Factor/@FindLinearRecurrence[l]

Square

Table[GraphData[{"Square",n},"RankPolynomial"][x,y],{n,3}]//Factor

Factor/@FindLinearRecurrence[l]

Star

l=Table[GraphData[{"Star",n},"RankPolynomial"][x,y],{n,4,20}]

Factor/@FindLinearRecurrence[l]

Sun

l=Table[GraphData[{"Sun",n},"RankPolynomial"][x,y],{n,3,5}]

Factor/@FindLinearRecurrence[l]

Sunlet

l=Table[GraphData[{"Sunlet",n},"RankPolynomial"][x,y],{n,3,6}]

FindLinearRecurrence[l]

FindPolynomialRecurrence[l,2]

Factor/@LinearRecurrence[{(1+x) (1+2 x),-x (((1+x))^3)},Take[l,2],4]

%==l

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

Table[GraphData[{"Sunlet",n},"RankPolynomial"][x,y],{n,3,7}]-Table[((((1+x))^n)+(x^(-1+n)) (-x+y))(((x+1))^n),{n,3,7}]//Expand

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

TraditionalForm[%]

Tetrahedral

Table[GraphData[{"Tetrahedral",n},"RankPolynomial"][x,y],{n,6,6}]//Factor

TorusGrid

l=Table[GraphData[{"TorusGrid",{n,n}},"RankPolynomial"][x,y],{n,3,4}]

Factor/@FindLinearRecurrence[l]

Triangular

l=Table[GraphData[{"Triangular",n},"RankPolynomial"][x,y],{n,3,4}]

Web

l=Append[Table[GraphData[{"Web",n},"RankPolynomial"][x,y],{n,3,6}],1+28 x+378 (x^2)+3276 (x^3)+20468 (x^4)+98112 (x^5)+374801 (x^6)+1169730 (x^7)+3032365 (x^8)+6601238 (x^9)+12146771 (x^10)+18944870 (x^11)+25019771 (x^12)+27829998 (x^13)+25789877 (x^14)+19549992 (x^15)+11783492 (x^16)+5408984 (x^17)+1766709 (x^18)+363692 (x^19)+35287 (x^20)+7 (x^3) y+168 (x^4) y+1939 (x^5) y+14303 (x^6) y+75579 (x^7) y+303898 (x^8) y+964096 (x^9) y+2468893 (x^10) y+5176297 (x^11) y+8948940 (x^12) y+12757014 (x^13) y+14868434 (x^14) y+13908552 (x^15) y+10133319 (x^16) y+5499291 (x^17) y+2076438 (x^18) y+483721 (x^19) y+52103 (x^20) y+7 (x^5) (y^2)+161 (x^6) (y^2)+1764 (x^7) (y^2)+12236 (x^8) (y^2)+60270 (x^9) (y^2)+224217 (x^10) (y^2)+653842 (x^11) (y^2)+1526575 (x^12) (y^2)+2872156 (x^13) (y^2)+4315402 (x^14) (y^2)+5061133 (x^15) (y^2)+4480301 (x^16) (y^2)+2862251 (x^17) (y^2)+1235920 (x^18) (y^2)+321217 (x^19) (y^2)+37828 (x^20) (y^2)+7 (x^7) (y^3)+147 (x^8) (y^3)+1470 (x^9) (y^3)+9373 (x^10) (y^3)+42994 (x^11) (y^3)+150150 (x^12) (y^3)+404866 (x^13) (y^3)+828352 (x^14) (y^3)+1249353 (x^15) (y^3)+1347549 (x^16) (y^3)+1002848 (x^17) (y^3)+487179 (x^18) (y^3)+138782 (x^19) (y^3)+17570 (x^20) (y^3)+7 (x^9) (y^4)+140 (x^10) (y^4)+1428 (x^11) (y^4)+9422 (x^12) (y^4)+41958 (x^13) (y^4)+123676 (x^14) (y^4)+240688 (x^15) (y^4)+310128 (x^16) (y^4)+261947 (x^17) (y^4)+139608 (x^18) (y^4)+42644 (x^19) (y^4)+5698 (x^20) (y^4)+21 (x^11) (y^5)+434 (x^12) (y^5)+3766 (x^13) (y^5)+15974 (x^14) (y^5)+38416 (x^15) (y^5)+56546 (x^16) (y^5)+52234 (x^17) (y^5)+29666 (x^18) (y^5)+9499 (x^19) (y^5)+1316 (x^20) (y^5)+14 (x^12) (y^6)+308 (x^13) (y^6)+1764 (x^14) (y^6)+4900 (x^15) (y^6)+7840 (x^16) (y^6)+7644 (x^17) (y^6)+4508 (x^18) (y^6)+1484 (x^19) (y^6)+210 (x^20) (y^6)+21 (x^13) (y^7)+147 (x^14) (y^7)+441 (x^15) (y^7)+735 (x^16) (y^7)+735 (x^17) (y^7)+441 (x^18) (y^7)+147 (x^19) (y^7)+21 (x^20) (y^7)+(x^13) (y^8)+7 (x^14) (y^8)+21 (x^15) (y^8)+35 (x^16) (y^8)+35 (x^17) (y^8)+21 (x^18) (y^8)+7 (x^19) (y^8)+(x^20) (y^8)]//Factor

Factor/@FindLinearRecurrence[l]

(ll=l/Table[(((x+1))^n),{n,3,7}]//Factor)

FindLinearRecurrence[l]

FindPolynomialRecurrence[l,5]

Wheel

l=Table[GraphData[{"Wheel",n},"RankPolynomial"][x,y],{n,4,13}]

Factor/@FindLinearRecurrence[l]

LinearRecurrence[{1+4 x+x y,-x (1+2 x) (2+y),(x^2) (1+x) (1+y)},{1+6 x+15 (x^2)+16 (x^3)+4 (x^2) y+15 (x^3) y+6 (x^3) (y^2)+(x^3) (y^3),1+8 x+28 (x^2)+52 (x^3)+45 (x^4)+4 (x^2) y+25 (x^3) y+52 (x^4) y+4 (x^3) (y^2)+28 (x^4) (y^2)+8 (x^4) (y^3)+(x^4) (y^4),1+10 x+45 (x^2)+115 (x^3)+170 (x^4)+121 (x^5)+5 (x^2) y+40 (x^3) y+126 (x^4) y+170 (x^5) y+5 (x^3) (y^2)+40 (x^4) (y^2)+115 (x^5) (y^2)+5 (x^4) (y^3)+45 (x^5) (y^3)+10 (x^5) (y^4)+(x^5) (y^5)},{21-3}]//Expand

GraphData[{"Wheel",5},"RankPolynomial"][x,y]

l-RecurrenceTable[{p[n]==(1+4 x+x y)p[n-1]+(-x (1+2 x) (2+y))p[n-2]+(x^2) (1+x) (1+y)p[n-3],p[4]==l[[1]],p[5]==l[[2]],p[6]==l[[3]]},p[n],{n,4,13}]//Expand

FullSimplify[RSolve[{p[n]==(1+4 x+x y)p[n-1]+(-x (1+2 x) (2+y))p[n-2]+(x^2) (1+x) (1+y)p[n-3],p[4]==l[[1]],p[5]==l[[2]],p[6]==l[[3]]},p[n],n],(x|y)∈Reals&&n>0&&n∈Integers]

(1/((x^2) (1+x) (1+y)))(2^(-1-n)) (-(2^(2+n)) (x^(2+n)) (1+y)+(2^(1+n)) (x^(1+n)) (-2+y) (1+y)+(2^(1+n)) (x^n) y (1+y)+(x^2) (3+y) ((((1+x (3+y)-(Sqrt[1+x (2-2 y+x (5+y (2+y)))])))^n)+(((1+x (3+y)+(Sqrt[1+x (2-2 y+x (5+y (2+y)))])))^n))+x ((((1+x (3+y)-(Sqrt[1+x (2-2 y+x (5+y (2+y)))])))^n)+(Sqrt[1+x (2-2 y+x (5+y (2+y)))]) (((1+x (3+y)-(Sqrt[1+x (2-2 y+x (5+y (2+y)))])))^n)+(((1+x (3+y)+(Sqrt[1+x (2-2 y+x (5+y (2+y)))])))^n)-(Sqrt[1+x (2-2 y+x (5+y (2+y)))]) (((1+x (3+y)+(Sqrt[1+x (2-2 y+x (5+y (2+y)))])))^n)))/.{(Sqrt[1+x (2-2 y+x (5+y (2+y)))]):>s}/.{x(3+y):>t}//FullSimplify

%/.x(3+y):>t//FullSimplify

rules=Thread[Table[GraphData[{"Wheel",n},"#"],{n,4,20}]->RecurrenceTable[{p[n]==(1+4 x+x y)p[n-1]+(-x (1+2 x) (2+y))p[n-2]+(x^2) (1+x) (1+y)p[n-3],p[4]==l[[1]],p[5]==l[[2]],p[6]==l[[3]]},p[n],{n,4,20}]]//Factor

Disconnected Graphs

Take[SortBy[GraphData["Disconnected"],GraphData[#,"V"]&],20]

GraphData[{5,7}]

GraphData[{5,7},"RankPolynomial"][x,y]

GraphData[{5,7},"ConnectedComponentGraphNames"]

Factor[Times@@(GraphData[#,"RankPolynomial"][x,y]&/@GraphData[{5,7},"ConnectedComponentGraphNames"])]

Select[

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

Times@@(GraphData[#,"RankPolynomial"][x,y]&/@GraphData[{5,7},"ConnectedComponentGraphNames"])

Co-Rank Graphs

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

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

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

TableForm[Take[Most[SortBy[ll,Max[First[#]]&]],-5],TableDepth->2]

TableForm[Take[SortBy[ll,Min[First[#]]&],30],TableDepth->2]