\documentclass[12pt,reqno]{article} \usepackage [colorlinks=true]{hyperref} \usepackage{fullpage} \usepackage{amsmath} \usepackage{amssymb} \usepackage{color} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\topmargin}{-.2in} \setlength{\textheight}{8.0in} \newtheorem{theorem}{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \newcommand{\proofend}{\hspace*{\fill}$\square$\normalsize} \begin{document} \makeatletter \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm {\LARGE\bf A Note on the Total Number of \\ \ \\ Double Eulerian Circuits in Multigraphs} \vskip 1cm \large Valery Liskovets\footnote{Supported in part by the INTAS (Grant INTAS-BELARUS 97-0093)} \vskip .5cm Institute of Mathematics\\ National Academy of Sciences \\ 220072, Minsk \\ Belarus \\ \href{mailto:liskov@im.bas-net.by}{\tt liskov@im.bas-net.by} \\ \vskip 1cm \end{center} \author{\protect{\bf Valery Liskovets\thanks{Supported in part by the INTAS (Grant INTAS-BELARUS 97-0093).}}\\ {\it Institute of Mathematics, National Academy of Sciences} \\ {\it 220072, Minsk, Belarus} \\ {\small\tt liskov@im.bas-net.by}} % \date{July 30, 2002} %%November 14, 2002 \date{} %\maketitle \begin{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. \end{abstract} \vskip .5in 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 {\it double eulerian circuits}. A multigraph possesses a double eulerian circuit if and only if it is connected. We deal with {\it labeled} multigraphs, that is, multigraphs with numbered vertices. Moreover, any vertex may be distinguished as a {\it root}. If a multigraph is unrooted, then vertex 1 implicitly plays the role of the root. %%The enumeration of eulerian circuits in digraphs is tractable unlike %%that in undirected graphs. All double eulerian circuits are considered as starting and finishing at the root. Two circuits are {\it 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)\cdots 5 \cdot 3 \cdot 1$. Our main result is the following. \begin{proposition} Up to equivalence, the total number $\varepsilon_n$ of double eulerian circuits in multigraphs with $n$ edges is equal to % $\ \displaystyle(2n-1)!!\,\frac{3^{n+1}-1}{2(n+1)}.$ \end{proposition} \bigskip Indeed, by a theorem of Lass \cite{Lass}, the number of such circuits\footnote{Some of the above definition details are implicit in \cite{Lass}.} in all {\sl rooted} multigraphs with $n$ edges and $m$ vertices is $\ (2n-1)!!\,2^{m-1}{n\choose 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. \proofend \bigskip The corresponding numerical values of $\varepsilon_n$ for $n=0,1,\dots,8$ are as follows: 1, 2, 13, 150, 2541, 57330, 1623105, 55405350, 2216439225. This is the sequence A069736 in Sloane \cite{Sloane}. The exponential generating function is $(\sqrt{1-2z}-\sqrt{1-6z})/2z.$ \bigskip \noindent {\bf 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\bar{a}1b2\bar{b})$ and $(1a2\bar{b}1b2\bar{a})$ where $a$ and $b$ are the two (interchangeable) edges considered as directed from 1 to 2, and $\bar{a}$ and $\bar{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\bar{a}1b1\bar{b}),\ (1a1b1\bar{a}1\bar{b})$ and $(1a1b1\bar{b}1\bar{a}).$ So, there are $4+2+4+3=13$ double eulerian circuits in all. %%3,3,2,2,1,1,1 \bigskip \noindent {\bf Remarks.} \medskip \noindent {\bf 1.} Asymptotically $\varepsilon_n$ grows as $\ C n^{-3/2}\,6^n\!\cdot\!n!,$ where $C=3/(2\sqrt{\pi}\,).$ %%$\frac{3\sqrt{2}}{2n}\Bigg(\frac{6n}{e}\Bigg)^n.$ \medskip \noindent {\bf 2.} By the same theorem of Lass, the total number $\varepsilon'_n$ of double eulerian circuits in {\sl rooted} labeled multigraphs with $n$ edges is equal to $\ (2n-1)!!\,3^n$; nume\-ri\-cally this is the sequence A011781 \cite{Sloane}: $1, 3, 27, 405, 8505, 229635, 7577955, 295540245,\cdots$ \medskip \noindent {\bf 3.} In contrast with topological maps, few closed formulae are known for the counting of abstract graphs (without isolated vertices) by the number of {\it edges}. \medskip \noindent {\bf 4.} Are there any similar results for other classes of graphs and different types of equivalence of eulerian circuits? \medskip \noindent {\bf 5.} At first glance, it seems as if we could use the same method to count double eulerian circuits {\sl 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|\varepsilon_n$ for odd $n$ (at the same time $\varepsilon_n$ is odd for even $n,$ so that $n$ does not divide $\varepsilon_n$ when $n$ is even.) %%Is there a combinatorial explanation? \bibstyle{plain} \begin{thebibliography}{xxx} \bibitem{Lass} B.\,Lass, D\'emonstration combinatoire de la formule de Harer~--~Zagier,\\ {\it C. R. Acad. Sci. Paris}, Serie I {\bf 333} (2001) No~3, 155--160. \vspace{-1.5ex} \bibitem{Sloane} N.\,J.\,A.\,Sloane, {\it On-Line Encyclopedia of Integer Sequences},\\ {\tt http://www.research.att.com/\~{}njas/sequences/} \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: 05C30, 05C45 \noindent \emph{Keywords: double eulerian circuit, symmetric multidigraph, labeled vertices, root } \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A011781} and \seqnum{A069736}.) \vspace*{+.1in} \noindent Received August 1 2002; revised version received November 14 2002. Published in {\it Journal of Integer Sequences} December 2 2002. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}. \end{document}