\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}