Enumerations of Unlabelled Multigraphs

Abstract

Using R. C. Read’s superposition method, we establish a formula for the enumeration of Euler multigraphs, with loops allowed and with given numbers of edges. In addition, applying Burnside’s Lemma and our adaptation of Read’s superposition method, we also derive a formula for the enumeration of Euler multigraphs without loops — via the calculation of the number of perfect matchings of the complement of complete multipartite graphs. MAPLE is employed to implement these enumerations. For one up to \(13\) edges, the numbers of nonisomorphic Euler multigraphs with loops allowed are:\(1, 3, 6, 16, 34, 90, 213, 572, 1499, 4231, 12115, 36660, 114105\) respectively, and for one up to \(16\) edges, the numbers of nonisomorphic Euler multigraphs without loops are:\(0, 1, 1, 4, 4, 15, 22, 68, 131, 376, 892, 2627, 7217, 22349, 69271, 229553\) respectively. Simplification of these methods yields the numbers of multigraphs with given numbers of edges, results which also appear to be new. Our methods also apply to multigraphs with essentially arbitrary constraints on vertex degrees.