An Algebraic Representation of Graphs and Applications to Graph Enumeration

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. 1. Introduction As pointed out in [1], generating graphs may be useful for numerous reasons. These include giving more insight into enumerative problems or the study of some properties of graphs. Problems of graph generation may also suggest conjectures or point out counterexamples. The use of generating functions (or functionals) in the enumeration or generation of graphs is standard practice both in mathematics and physics [2–4]. However, this is by no means obligatory since any method of manipulating graphs may be used. Furthermore, the problem of generating graphs taking into account their symmetries was considered as early as the 19th century [5] and more recently for instance, in [6]. In particular, in quantum field theory, generated graphs are weighted by scalars given by the inverses of the orders of their groups of automorphisms [4]. In [7, 8], this was handled for trees and connected multigraphs (with multiple edges and loops allowed), on the level of the symmetric algebra on the vector space of time-ordered field operators. The underlying structure is an algebraic graph representation subsequently developed in [9]. In this representation, graphs are associated with tensors whose indices correspond to the vertex numbers. In the former papers, this made it possible to derive recursion formulas to produce larger graphs from smaller ones by increasing by 1 the number of their vertices or the number of their edges. An interesting property of these formulas is that of satisfying alternative recurrences which relate either a tree or connected multigraph on vertices with all pairs of their connected subgraphs with total number of vertices equal to . In the case of trees, the algorithmic description of the corresponding formula is about the same as that used by Dziobek in his induction proof of Cayley’s formula [10, 11]. Accordingly, the formula induces a recurrence for , that is, the sum of the inverses of the orders of the groups of automorphisms of all the equivalence classes of trees on vertices [12, page 209]. For simplicity, here by graphs we mean simple graphs. However, our results generalize