An Algebraic Representation of Graphs and Applications to Graph Enumeration

Abstract EN

We give a recursion formula to generate all the equivalence classes of connected graphs with coefficients given by the inverses of the orders of their groups of automorphisms.

We use an algebraic graph representation to apply the result to the enumeration of connected graphs, all of whose biconnected components have the same number of vertices and edges.

The proof uses Abel’s binomial theorem and generalizes Dziobek’s induction proof of Cayley’s formula.