Copyright © 2013 Ângela Mestre. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

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.