A Note on the Total Number of

Double Eulerian Circuits in Multigraphs

Valery Liskovets^{1}

Institute of Mathematics National Academy of Sciences 220072, Minsk Belarus

                     liskov@im.bas-net.by

Abstract

We formulate explicitly and discuss a simple new enumerative formula for double (directed) eulerian circuits in n-edged labeled multigraphs. The formula follows easily from a recent 2-parametric formula of B. Lass.

Multigraphs may have loops and are considered as symmetric multidigraphs. So, in an eulerian circuit, every edge is traversed exactly once in each direction (backtracks are allowed). With respect to undirected multigraphs such circuits are called here double eulerian circuits. A multigraph possesses a double eulerian circuit if and only if it is connected. We deal with labeled multigraphs, that is, multigraphs with numbered vertices. Moreover, any vertex may be distinguished as a root. If a multigraph is unrooted, then vertex 1 implicitly plays the role of the root.

1Supported in part by the INTAS (Grant INTAS-BELARUS 97-0093)

All double eulerian circuits are considered as starting and finishing at the root. Two circuits are equivalent if they differ only in the order in which parallel edges (including loops) or loops in both directions are traversed.

We define (2n − 1)!! = (2n − 1)(2n − 3) ⋯ 5 · 3 · 1. Our main result is the following.

Proposition 1 Up to equivalence, the total number ε_{n} of double eulerian circuits in multi-

graphs with n edges is equal to (2n − 1)!! \frac{3^{n+1} − 1}{2(n + 1)}.

Indeed, by a theorem of Lass [1], the number of such circuits^{2} in all rooted multigraphs with n edges and m vertices is (2n − 1)!! 2^{m−1}\binom{n}{m−1}. Since the vertices are labeled, the number of rootings is equal to m. Dividing the above formula by m and summing over all m we arrive at the desired expression. □

The corresponding numerical values of ε_{n} for n = 0, 1, …, 8 are as follows: 1, 2, 13, 150, 2541, 57330, 1623105, 55405350, 2216439225. This is the sequence A069736 in Sloane [2]. The exponential generating function is (\sqrt{1 − 2z} − \sqrt{1 − 6z})/2z.

Example. n = 2. There are 4 unlabeled connected multigraphs with 2 edges. A graph on 3 vertices (path) with vertex 1 at an end (there are two such graphs) has only one double eulerian circuit. The same graph rooted at the middle vertex has two circuits. The graph consisting of two vertices and two parallel edges (“lune”) also has two different circuits: (1a2ā1b2b̄) and (1a2b̄1b2ā) where a and b are the two (interchangeable) edges considered as directed from 1 to 2, and ā and b̄ are the same edges in the opposite direction. Likewise, the graph with two vertices and one loop has three double eulerian circuits if the vertex with the loop is labeled 1; otherwise the circuit is unique up to equivalence. Finally, the 1-vertex graph with two loops contains three different circuits: (1a1ā1b1b̄), (1a1b1ā1b̄) and (1a1b1b̄1ā). So, there are 4 + 2 + 4 + 3 = 13 double eulerian circuits in all.

Remarks.

1. Asymptotically ε_{n} grows as Cn^{−3/2} 6^{n}·n!, where C = 3/(2\sqrt{π}).

2. By the same theorem of Lass, the total number ε′_{n} of double eulerian circuits in rooted labeled multigraphs with n edges is equal to (2n − 1)!! 3^{n}; numerically this is the sequence A011781 [2]: 1, 3, 27, 405, 8505, 229635, 7577955, 295540245, ⋯

3. In contrast with topological maps, few closed formulae are known for the counting of abstract graphs (without isolated vertices) by the number of edges.

2Some of the above definition details are implicit in [1].

4. Are there any similar results for other classes of graphs and different types of equivalence of eulerian circuits?

5. At first glance, it seems as if we could use the same method to count double eulerian circuits regardless of rooting since every double eulerian circuit has one and the same number n of possible starting pairs (root, incident edge). Accordingly, the contribution to the total sum from any vertex taken as the root seems to be proportional to its valency. This idea, however, can be seen to fail because of multiple edges, loops and the definition of equivalence between circuits; cf. the example above. Nevertheless n|ε_{n} for odd n (at the same time ε_{n} is odd for even n, so that n does not divide ε_{n} when n is even.)

References

[1] B. Lass, Démonstration combinatoire de la formule de Harer – Zagier, C. R. Acad. Sci. Paris, Serie I 333 (2001) No 3, 155–160.

[2] N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences,

     http://www.research.att.com/~njas/sequences/

2000 Mathematics Subject Classification: 05C30, 05C45 Keywords: double eulerian circuit, symmetric multidigraph, labeled vertices, root

(Concerned with sequences \underline{A011781} and \underline{A069736}.)

Received August 1 2002; revised version received November 14 2002. Published in Journal of Integer Sequences December 2 2002.

Return to Journal of Integer Sequences home page.