Reciprocal Ihara zeta polynomials of connected graphs

edit · history · discussion · files · long url · combinatorics polynomial

Polynomials

$G$

$P_G(u)$

Bw:

u^6 - 2*u^3 + 1

comment: The cycle graph $C_3$. The complete graph $K_3$.

C]:

u^8 - 2*u^4 + 1

comment: The cycle graph $C_4$.

C^:

-4*u^10 + u^8 + 4*u^7 + 4*u^6 - 2*u^4 - 4*u^3 + 1

comment: The diamond graph, obtained by deleting one edge from $K_4$.

C~:

16*u^12 - 24*u^10 - 16*u^9 - 3*u^8 + 24*u^7 + 16*u^6 - 6*u^4 - 8*u^3 + 1

comment: The complete graph $K_4$.

DLo:

u^10 - 2*u^5 + 1

comment: The cycle graph $C_5$.

DFw:

-4*u^12 + 9*u^8 - 6*u^4 + 1

comment: The complete bipartite graph $K_{2,3}$.

DK{:

-3*u^12 + 4*u^9 + 2*u^6 - 4*u^3 + 1

comment: The bowtie graph, consisting of two triangles sharing one vertex.

Dbk:

-4*u^12 + u^10 + 2*u^9 + 3*u^8 + 2*u^7 + u^6 - 2*u^5 - 2*u^4 - 2*u^3 + 1

DF{:

9*u^14 - 4*u^12 - 6*u^11 - 18*u^10 + 9*u^8 + 12*u^7 + 9*u^6 - 6*u^4 - 6*u^3 + 1

DL{:

12*u^14 - 11*u^12 - 10*u^11 - 11*u^10 + 6*u^9 + 6*u^8 + 12*u^7 + 7*u^6 - 2*u^5 - 4*u^4 - 6*u^3 + 1

DNw:

16*u^14 - 20*u^12 - 8*u^11 - 12*u^10 + 4*u^9 + 17*u^8 + 12*u^7 + 4*u^6 - 4*u^5 - 6*u^4 - 4*u^3 + 1

DN{:

-36*u^16 + 73*u^14 + 28*u^13 - 4*u^12 - 50*u^11 - 62*u^10 - 8*u^9 + 17*u^8 + 44*u^7 + 21*u^6 - 4*u^5 - 10*u^4 - 10*u^3 + 1

D]{:

-48*u^16 + 112*u^14 + 32*u^13 - 40*u^12 - 64*u^11 - 68*u^10 + 8*u^9 + 41*u^8 + 40*u^7 + 12*u^6 - 8*u^5 - 10*u^4 - 8*u^3 + 1

D^{:

108*u^18 - 360*u^16 - 80*u^15 + 345*u^14 + 252*u^13 + 52*u^12 - 222*u^11 - 234*u^10 - 32*u^9 + 69*u^8 + 108*u^7 + 37*u^6 - 12*u^5 - 18*u^4 - 14*u^3 + 1

D~{:

-243*u^20 + 1080*u^18 + 180*u^17 - 1710*u^16 - 776*u^15 + 870*u^14 + 1200*u^13 + 505*u^12 - 660*u^11 - 708*u^10 - 140*u^9 + 165*u^8 + 240*u^7 + 70*u^6 - 24*u^5 - 30*u^4 - 20*u^3 + 1

comment: The complete graph $K_5$.

EIe_:

u^12 - 2*u^6 + 1

comment: The cycle graph $C_6$.

EKNG:

-4*u^14 + u^12 + 4*u^10 + 4*u^8 - 2*u^6 - 4*u^4 + 1

EK`w:

-3*u^14 + 2*u^11 + 2*u^10 + u^8 + u^6 - 2*u^4 - 2*u^3 + 1

E_]o:

-4*u^14 + 4*u^10 + 4*u^9 + u^8 - 4*u^5 - 2*u^4 + 1

E`NG:

-4*u^14 + u^12 + 8*u^11 - 4*u^9 - 4*u^8 + 6*u^6 - 4*u^3 + 1

comment: The barbell graph consisting of two triangles joined by a bridge.

EoLW:

-4*u^14 + u^12 + 2*u^11 + u^10 + 2*u^9 + 2*u^8 - u^6 - 2*u^5 - 2*u^3 + 1

E?~o:

9*u^16 - 28*u^12 + 30*u^8 - 12*u^4 + 1

comment: The complete bipartite graph $K_{2,4}$.

EBjW:

12*u^16 - 8*u^14 - 8*u^13 - 12*u^12 + 12*u^9 + 9*u^8 + 4*u^7 - 4*u^5 - 2*u^4 - 4*u^3 + 1

EBn_:

16*u^16 - 16*u^14 - 4*u^13 - 15*u^12 - 6*u^11 + 9*u^10 + 14*u^9 + 10*u^8 + 4*u^7 - u^6 - 6*u^5 - 4*u^4 - 2*u^3 + 1

EENg:

12*u^16 - 7*u^14 - 4*u^13 - 20*u^12 - 2*u^11 + 6*u^10 + 8*u^9 + 13*u^8 + 4*u^7 + u^6 - 4*u^5 - 6*u^4 - 2*u^3 + 1

EImo:

16*u^16 - 16*u^14 - 24*u^12 + 12*u^10 + 25*u^8 - 4*u^6 - 10*u^4 + 1

EJeg:

16*u^16 - 16*u^14 - 16*u^13 - 8*u^12 + 16*u^11 + 4*u^10 + 4*u^9 + u^8 + 4*u^7 + 4*u^6 - 4*u^5 - 2*u^4 - 4*u^3 + 1

E_Nw:

8*u^16 - 3*u^14 - 8*u^13 - 8*u^12 + 2*u^11 - 2*u^10 + 8*u^9 + u^8 + 4*u^7 + 5*u^6 - 2*u^4 - 6*u^3 + 1

E_]w:

9*u^16 - 4*u^14 - 4*u^13 - 12*u^12 - 4*u^11 + 8*u^9 + 6*u^8 + 8*u^7 + 4*u^6 - 4*u^5 - 4*u^4 - 4*u^3 + 1

E`NW:

12*u^16 - 11*u^14 - 16*u^13 - 4*u^12 + 18*u^11 + 2*u^10 - 7*u^8 + 4*u^7 + 9*u^6 - 2*u^4 - 6*u^3 + 1

E`]o:

16*u^16 - 20*u^14 - 8*u^13 - 4*u^10 + 12*u^9 + 9*u^8 + 4*u^7 - 4*u^5 - 2*u^4 - 4*u^3 + 1

EaMw:

12*u^16 - 11*u^14 - 6*u^13 - 9*u^12 + 2*u^11 + u^10 + 4*u^9 + 8*u^8 + 6*u^7 + 2*u^6 - 2*u^5 - 4*u^4 - 4*u^3 + 1

E?~w:

-16*u^18 + 9*u^16 + 8*u^15 + 48*u^14 - 28*u^12 - 24*u^11 - 48*u^10 + 30*u^8 + 24*u^7 + 16*u^6 - 12*u^4 - 8*u^3 + 1

E@vw:

-24*u^18 + 29*u^16 + 16*u^15 + 36*u^14 - 12*u^13 - 40*u^12 - 32*u^11 - 24*u^10 + 16*u^9 + 18*u^8 + 24*u^7 + 12*u^6 - 4*u^5 - 8*u^4 - 8*u^3 + 1

E@~o:

-36*u^18 + 57*u^16 + 12*u^15 + 44*u^14 - 8*u^13 - 92*u^12 - 28*u^11 - 12*u^10 + 16*u^9 + 46*u^8 + 20*u^7 + 4*u^6 - 8*u^5 - 12*u^4 - 4*u^3 + 1

EBjw:

-32*u^18 + 52*u^16 + 24*u^15 + 16*u^14 - 32*u^13 - 40*u^12 - 20*u^11 - 16*u^10 + 20*u^9 + 17*u^8 + 20*u^7 + 8*u^6 - 4*u^5 - 6*u^4 - 8*u^3 + 1

EBnW:

-27*u^18 + 36*u^16 + 20*u^15 + 30*u^14 - 18*u^13 - 36*u^12 - 36*u^11 - 27*u^10 + 24*u^9 + 21*u^8 + 24*u^7 + 8*u^6 - 6*u^5 - 6*u^4 - 8*u^3 + 1

EFz_:

-64*u^18 + 144*u^16 - 168*u^12 + 36*u^10 + 81*u^8 - 12*u^6 - 18*u^4 + 1

comment: The complete bipartite graph $K_{3,3}$.

EHuw:

-36*u^18 + 61*u^16 + 18*u^15 + 21*u^14 - 16*u^13 - 60*u^12 - 34*u^11 - 14*u^10 + 24*u^9 + 30*u^8 + 22*u^7 + 5*u^6 - 8*u^5 - 8*u^4 - 6*u^3 + 1

EImw:

-36*u^18 + 64*u^16 + 16*u^15 + 17*u^14 - 20*u^13 - 60*u^12 - 14*u^11 - 18*u^10 + 8*u^9 + 37*u^8 + 20*u^7 + 5*u^6 - 4*u^5 - 10*u^4 - 6*u^3 + 1

EIno:

-48*u^18 + 96*u^16 + 16*u^15 + 4*u^14 - 16*u^13 - 88*u^12 - 28*u^11 + 4*u^10 + 24*u^9 + 41*u^8 + 16*u^7 - 8*u^5 - 10*u^4 - 4*u^3 + 1

EJqw:

-48*u^18 + 96*u^16 + 36*u^15 - 15*u^14 - 64*u^13 - 48*u^12 + 2*u^11 - 6*u^10 + 24*u^9 + 21*u^8 + 16*u^7 + 5*u^6 - 8*u^5 - 6*u^4 - 6*u^3 + 1

EK]w:

-36*u^18 + 64*u^16 + 32*u^15 + 4*u^14 - 56*u^13 - 40*u^12 + 4*u^11 - 4*u^10 + 12*u^9 + 5*u^8 + 20*u^7 + 12*u^6 - 4*u^5 - 6*u^4 - 8*u^3 + 1

ELpw:

-48*u^18 + 100*u^16 + 24*u^15 - 23*u^14 - 28*u^13 - 44*u^12 - 34*u^11 - 10*u^10 + 36*u^9 + 29*u^8 + 16*u^7 + u^6 - 8*u^5 - 6*u^4 - 6*u^3 + 1

ELv_:

-64*u^18 + 144*u^16 + 32*u^15 - 48*u^14 - 48*u^13 - 72*u^12 - 24*u^11 + 24*u^10 + 44*u^9 + 21*u^8 + 12*u^7 - 12*u^5 - 6*u^4 - 4*u^3 + 1

comment: The triangular prism graph.

E`Nw:

-32*u^18 + 60*u^16 + 36*u^15 - 15*u^14 - 72*u^13 - 8*u^12 + 30*u^11 - 6*u^10 - 8*u^9 - 15*u^8 + 24*u^7 + 21*u^6 - 6*u^4 - 10*u^3 + 1

E`]w:

-36*u^18 + 73*u^16 + 20*u^15 - 20*u^14 - 28*u^13 - 16*u^12 - 8*u^11 - 20*u^10 + 14*u^8 + 28*u^7 + 12*u^6 - 4*u^5 - 8*u^4 - 8*u^3 + 1

E@~w:

64*u^20 - 148*u^18 - 40*u^17 - 11*u^16 + 76*u^15 + 228*u^14 + 40*u^13 - 88*u^12 - 132*u^11 - 108*u^10 + 8*u^9 + 50*u^8 + 68*u^7 + 28*u^6 - 8*u^5 - 16*u^4 - 12*u^3 + 1

EBnw:

72*u^20 - 179*u^18 - 48*u^17 + 36*u^16 + 100*u^15 + 194*u^14 + 22*u^13 - 80*u^12 - 140*u^11 - 103*u^10 + 20*u^9 + 49*u^8 + 68*u^7 + 24*u^6 - 10*u^5 - 14*u^4 - 12*u^3 + 1

EB~o:

108*u^20 - 312*u^18 - 48*u^17 + 169*u^16 + 104*u^15 + 248*u^14 + 16*u^13 - 228*u^12 - 152*u^11 - 72*u^10 + 48*u^9 + 94*u^8 + 56*u^7 + 8*u^6 - 16*u^5 - 16*u^4 - 8*u^3 + 1

EInw:

96*u^20 - 268*u^18 - 56*u^17 + 132*u^16 + 132*u^15 + 209*u^14 - 20*u^13 - 160*u^12 - 130*u^11 - 82*u^10 + 40*u^9 + 73*u^8 + 56*u^7 + 13*u^6 - 12*u^5 - 14*u^4 - 10*u^3 + 1

EJmw:

81*u^20 - 216*u^18 - 60*u^17 + 90*u^16 + 152*u^15 + 170*u^14 - 64*u^13 - 99*u^12 - 76*u^11 - 76*u^10 + 4*u^9 + 37*u^8 + 64*u^7 + 26*u^6 - 8*u^5 - 14*u^4 - 12*u^3 + 1

EJnW:

108*u^20 - 315*u^18 - 74*u^17 + 207*u^16 + 194*u^15 + 147*u^14 - 90*u^13 - 140*u^12 - 110*u^11 - 69*u^10 + 50*u^9 + 60*u^8 + 54*u^7 + 13*u^6 - 14*u^5 - 12*u^4 - 10*u^3 + 1

EK^w:

96*u^20 - 276*u^18 - 76*u^17 + 181*u^16 + 208*u^15 + 112*u^14 - 128*u^13 - 100*u^12 - 60*u^11 - 52*u^10 + 20*u^9 + 26*u^8 + 56*u^7 + 24*u^6 - 8*u^5 - 12*u^4 - 12*u^3 + 1

EK~o:

144*u^20 - 456*u^18 - 96*u^17 + 393*u^16 + 280*u^15 + 88*u^14 - 208*u^13 - 204*u^12 - 56*u^11 - 24*u^10 + 64*u^9 + 62*u^8 + 40*u^7 + 8*u^6 - 16*u^5 - 12*u^4 - 8*u^3 + 1

ELrw:

128*u^20 - 400*u^18 - 80*u^17 + 340*u^16 + 212*u^15 + 65*u^14 - 100*u^13 - 140*u^12 - 130*u^11 - 54*u^10 + 80*u^9 + 65*u^8 + 40*u^7 + 5*u^6 - 12*u^5 - 10*u^4 - 10*u^3 + 1

ER^W:

108*u^20 - 324*u^18 - 56*u^17 + 232*u^16 + 132*u^15 + 129*u^14 - 20*u^13 - 140*u^12 - 130*u^11 - 74*u^10 + 40*u^9 + 69*u^8 + 56*u^7 + 13*u^6 - 12*u^5 - 14*u^4 - 10*u^3 + 1

Ek]w:

144*u^20 - 460*u^18 - 80*u^17 + 401*u^16 + 216*u^15 + 92*u^14 - 112*u^13 - 220*u^12 - 120*u^11 - 20*u^10 + 80*u^9 + 70*u^8 + 40*u^7 + 4*u^6 - 16*u^5 - 12*u^4 - 8*u^3 + 1

Es\w:

144*u^20 - 460*u^18 - 48*u^17 + 360*u^16 + 120*u^15 + 225*u^14 - 36*u^13 - 348*u^12 - 102*u^11 - 18*u^10 + 48*u^9 + 117*u^8 + 36*u^7 - 3*u^6 - 12*u^5 - 18*u^4 - 6*u^3 + 1

EB~w:

-192*u^22 + 716*u^20 + 120*u^19 - 744*u^18 - 404*u^17 - 255*u^16 + 320*u^15 + 824*u^14 + 276*u^13 - 188*u^12 - 440*u^11 - 312*u^10 + 20*u^9 + 134*u^8 + 144*u^7 + 40*u^6 - 20*u^5 - 24*u^4 - 16*u^3 + 1

EFzw:

-288*u^22 + 1188*u^20 + 144*u^19 - 1588*u^18 - 528*u^17 + 273*u^16 + 564*u^15 + 1044*u^14 + 72*u^13 - 612*u^12 - 420*u^11 - 204*u^10 + 96*u^9 + 198*u^8 + 108*u^7 + 12*u^6 - 24*u^5 - 24*u^4 - 12*u^3 + 1

EJnw:

-216*u^22 + 837*u^20 + 148*u^19 - 992*u^18 - 536*u^17 + 2*u^16 + 560*u^15 + 702*u^14 + 76*u^13 - 199*u^12 - 380*u^11 - 268*u^10 + 32*u^9 + 117*u^8 + 136*u^7 + 38*u^6 - 20*u^5 - 22*u^4 - 16*u^3 + 1

EJ~o:

-243*u^22 + 972*u^20 + 126*u^19 - 1224*u^18 - 432*u^17 + 105*u^16 + 364*u^15 + 834*u^14 + 264*u^13 - 332*u^12 - 480*u^11 - 288*u^10 + 64*u^9 + 174*u^8 + 132*u^7 + 25*u^6 - 24*u^5 - 24*u^4 - 14*u^3 + 1

EK~w:

-256*u^22 + 1040*u^20 + 192*u^19 - 1400*u^18 - 752*u^17 + 385*u^16 + 976*u^15 + 600*u^14 - 304*u^13 - 324*u^12 - 240*u^11 - 136*u^10 + 48*u^9 + 70*u^8 + 112*u^7 + 40*u^6 - 16*u^5 - 20*u^4 - 16*u^3 + 1

EL~o:

-324*u^22 + 1368*u^20 + 192*u^19 - 1968*u^18 - 740*u^17 + 713*u^16 + 908*u^15 + 760*u^14 - 148*u^13 - 556*u^12 - 420*u^11 - 144*u^10 + 148*u^9 + 158*u^8 + 100*u^7 + 12*u^6 - 28*u^5 - 20*u^4 - 12*u^3 + 1

Ebnw:

-288*u^22 + 1196*u^20 + 180*u^19 - 1671*u^18 - 686*u^17 + 539*u^16 + 822*u^15 + 675*u^14 - 106*u^13 - 412*u^12 - 390*u^11 - 177*u^10 + 110*u^9 + 136*u^8 + 106*u^7 + 21*u^6 - 22*u^5 - 20*u^4 - 14*u^3 + 1

Ejmw:

-324*u^22 + 1377*u^20 + 168*u^19 - 1992*u^18 - 636*u^17 + 710*u^16 + 744*u^15 + 822*u^14 - 48*u^13 - 611*u^12 - 420*u^11 - 148*u^10 + 132*u^9 + 177*u^8 + 96*u^7 + 10*u^6 - 24*u^5 - 22*u^4 - 12*u^3 + 1

EF~w:

512*u^24 - 2592*u^22 - 304*u^21 + 4788*u^20 + 1440*u^19 - 3076*u^18 - 2412*u^17 - 1467*u^16 + 1236*u^15 + 2844*u^14 + 900*u^13 - 648*u^12 - 1116*u^11 - 684*u^10 + 60*u^9 + 306*u^8 + 252*u^7 + 52*u^6 - 36*u^5 - 36*u^4 - 20*u^3 + 1

EJ~w:

432*u^24 - 2115*u^22 - 284*u^21 + 3672*u^20 + 1314*u^19 - 1900*u^18 - 2088*u^17 - 1719*u^16 + 816*u^15 + 2214*u^14 + 1152*u^13 - 60*u^12 - 1116*u^11 - 828*u^10 - 24*u^9 + 270*u^8 + 288*u^7 + 69*u^6 - 36*u^5 - 36*u^4 - 22*u^3 + 1

EL~w:

576*u^24 - 2980*u^22 - 376*u^21 + 5784*u^20 + 1848*u^19 - 4468*u^18 - 3348*u^17 - 363*u^16 + 2316*u^15 + 2436*u^14 + 300*u^13 - 720*u^12 - 1044*u^11 - 540*u^10 + 132*u^9 + 258*u^8 + 228*u^7 + 48*u^6 - 36*u^5 - 32*u^4 - 20*u^3 + 1

ENzw:

648*u^24 - 3411*u^22 - 384*u^21 + 6804*u^20 + 1894*u^19 - 5588*u^18 - 3448*u^17 + u^16 + 2400*u^15 + 2814*u^14 + 328*u^13 - 1084*u^12 - 1156*u^11 - 500*u^10 + 216*u^9 + 318*u^8 + 208*u^7 + 29*u^6 - 40*u^5 - 32*u^4 - 18*u^3 + 1

E]~o:

729*u^24 - 3888*u^22 - 432*u^21 + 7938*u^20 + 2160*u^19 - 6912*u^18 - 4032*u^17 + 639*u^16 + 3008*u^15 + 2976*u^14 + 96*u^13 - 1412*u^12 - 1248*u^11 - 384*u^10 + 320*u^9 + 327*u^8 + 192*u^7 + 16*u^6 - 48*u^5 - 30*u^4 - 16*u^3 + 1

comment: The octahedral graph.

EN~w:

-1152*u^26 + 7208*u^24 + 732*u^23 - 18111*u^22 - 4396*u^21 + 21900*u^20 + 10518*u^19 - 9724*u^18 - 12000*u^17 - 5271*u^16 + 5040*u^15 + 7230*u^14 + 2184*u^13 - 1284*u^12 - 2604*u^11 - 1356*u^10 + 192*u^9 + 534*u^8 + 420*u^7 + 73*u^6 - 60*u^5 - 48*u^4 - 26*u^3 + 1

E]~w:

-1296*u^26 + 8217*u^24 + 792*u^23 - 21072*u^22 - 4800*u^21 + 26482*u^20 + 11656*u^19 - 13408*u^18 - 13696*u^17 - 4417*u^16 + 6384*u^15 + 8224*u^14 + 1792*u^13 - 2148*u^12 - 2800*u^11 - 1168*u^10 + 384*u^9 + 583*u^8 + 376*u^7 + 48*u^6 - 64*u^5 - 46*u^4 - 24*u^3 + 1

E^~w:

2304*u^28 - 16992*u^26 - 1440*u^25 + 52661*u^24 + 10272*u^23 - 86376*u^22 - 30688*u^21 + 73902*u^20 + 48480*u^19 - 18400*u^18 - 40512*u^17 - 22281*u^16 + 12096*u^15 + 19920*u^14 + 6720*u^13 - 3084*u^12 - 5952*u^11 - 2688*u^10 + 480*u^9 + 1011*u^8 + 672*u^7 + 88*u^6 - 96*u^5 - 66*u^4 - 32*u^3 + 1

E~~w:

-4096*u^30 + 34560*u^28 + 2560*u^27 - 126000*u^26 - 21024*u^25 + 255165*u^24 + 74520*u^23 - 301320*u^22 - 146960*u^21 + 183798*u^20 + 171000*u^19 - 5440*u^18 - 109440*u^17 - 74745*u^16 + 21168*u^15 + 46800*u^14 + 18720*u^13 - 5180*u^12 - 12240*u^11 - 5328*u^10 + 800*u^9 + 1755*u^8 + 1080*u^7 + 120*u^6 - 144*u^5 - 90*u^4 - 40*u^3 + 1

comment: The complete graph $K_6$.

Definition

The reciprocal Ihara zeta polynomial of a finite simple connected graph $G$ with minimum vertex degree at least two is $P_G(u)=Z_G(u)^{-1}$, where $Z_G$ is the ordinary Ihara zeta function [2].

Parameters

$G$

— graph (a finite simple undirected connected graph with minimum vertex degree at least two, identified by its canonical graph6 string)

Formulas

(1)

$P_G(u)=\prod_{[C]}(1-u^{\ell(C)})$, where $[C]$ ranges over primitive closed walks without backtracking or a tail, modulo cyclic rotation. The product is interpreted as a formal power series [1].

(2)

$P_G(u)=\det(I_{2m}-uB)=(1-u^2)^{m-n}\det(I_n-uA+u^2(D-I_n))$ [2].

(3)

$P_{C_n}(u)=(1-u^n)^2$ for the cycle graph $C_n$, since its two orientations give its two primitive closed walks.

(4)

$\deg P_G=2m$ and $[u^{2m}]P_G(u)=(-1)^{m-n}\prod_{v\in V(G)}(\deg v-1)$ [1].

Comments

(5)

A closed walk is primitive if it is not a power of a shorter closed walk. Backtracking means that an edge is immediately followed by its reverse; a tail means that the last edge is the reverse of the first. Primitive walks without backtracking or a tail are identified under cyclic rotation, but not reversal of orientation [1]. Every edge has length and weight one, and $\ell(C)$ counts the edges traversed. These conventions also apply to walks that traverse a bridge.

(6)

The graph6 encoding [3] is taken after Sage canonical relabelling: G.canonical_label(algorithm="sage").graph6_string(). Decode an identifier with Graph(identifier). The identifiers agree with the adjacency characteristic polynomial table and the Laplacian polynomial table on their common domain.

(7)

The stored polynomial is expanded in $u$ with constant coefficient one. All factors at $u=1$ and $u=-1$ are retained. Attaching a tree to a graph does not change its primitive closed walks, which motivates the minimum degree restriction; graphs with bridges are still included.

(8)

Write $n=|V(G)|$ and $m=|E(G)|$, counting unoriented edges. Let $A$ be the adjacency matrix and $D=\operatorname{diag}(\deg v)$. The matrix $B$ is indexed by the $2m$ directed edges, with $B_{e,f}=1$ when the endpoint of $e$ is the start of $f$ and $f\ne\bar e$, where $\bar e$ reverses $e$; all other entries are zero.

(9)

Rows are ordered by vertex count, edge count and graph6 bytes. Distinct graph identities remain separate even when their polynomials agree.

Programs

(P1)

Sage

G = Graph('Bw')  # the triangle
arcs = [(a, b) for a in G for b in G.neighbors(a)]
s = len(arcs)
B = matrix(ZZ, s, s, [int(v == x and w != y)
                      for w, v in arcs for x, y in arcs])
c = B.charpoly()
R = PolynomialRing(ZZ, 'u')
R(list(reversed(c.list())))

References

[1]

T. Hasegawa and S. Saito, On a prime zeta function of a graph, Pacific Journal of Mathematics 273 (2015), 123–146. Definitions on pp. 125–126 and Facts 1(4) on p. 128. (doi)

[2]

I. Sato, The Ihara Zeta function and Quantum Walk, RIMS Kokyuroku 2120 (2019), 199–219. Theorem 3 and the four-vertex example. https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/2120-10.pdf

Links

[3]

Brendan McKay: graph6 and sparse6 formats

Similar tables

Characteristic polynomials of connected graphs — uses the same graph6 identifiers and holds $\det(xI-A)$ for the adjacency matrix in the Ihara determinant formula

Laplacian polynomials of connected graphs — uses the same graph6 identifiers and the same adjacency and degree matrices, through $L=D-A$

Data properties

Entries are of type: integral polynomial

How well the digits are known: exact

Table is complete: no (it holds all 76 isomorphism classes of simple connected graphs with minimum degree at least two and three through six vertices; this noncanonical size bound gives complete small-graph coverage of cycles, regular and irregular graphs, and graphs with bridges, with short readable polynomials rather than a selection limited to named examples)

How they were obtained:

The generator enumerates all eligible graphs through six vertices with nauty and uses exact integer polynomial arithmetic to expand the Bass determinant over permutations. Independently, the integer directed-edge matrix characteristic polynomial gives the same reciprocal on all 76 rows. The NetworkX graph atlas gives the same 76 graph classes, and all identifiers agree with T237 and T238.

The cycle formula, degree and leading coefficient are checked on every applicable row. Direct enumeration of rooted, oriented, reduced closed walks agrees with the coefficients of $-uP_G\prime(u)/P_G(u)$ at lengths one through six for every graph. Cycle graphs and a single edge provide controls, and the diamond polynomial agrees with the factorization in [2], p. 204. Exactness and size checks pass; the longest written polynomial has 334 characters. No decimal approximation or precision choice is involved.