Graph enumeration

• Assign a label xi to each node

• x1x22x32x4x54x63x73x84x9x1

• deg. seq. d = (1,2,2,1,4,3,3,3,4,1,1)

• ? di = 2 * edges

?ji=1 ?Nj=1 = ? n(d) x1d1 . . . xndn

(1 + xixj)

x10

• How to cope with the combinatorial explosion?

E.g., for n = 10, the product has 245 terms

Previous slide

Next slide

Back to first slide

View graphic version