Refined Bounds on the Number of Eulerian Tours in Undirected Graphs

Given an undirected multigraph G = (V, E) with no self-loops, and one of its nodes s. V, we consider the #P-complete problem of counting the number ET (e) s ( G) of its Eulerian tours starting and ending at node s. We provide lower and upper bounds on the size of ET (e) s (G). Namely, let d( v) denote the degree of a node v. V; we show that max{L (e) 1, L (e) 2} = |ET (e) s (G)| = d(s) v.V (d( v) - 1)!! where L (e) 1 = (d(s) - 1)!! v.V\s (d(v) - 2)!! and L (e) 2 = 21-|V|+| E|. We also consider the notion of node-distinct Eulerian tours. Indeed, the classical Eulerian tours are edge-distinct sequences. Node-distinct Eulerian tours, denoted ET (n) s (G), should instead be different as node sequences. Let (u) be the number of distinct neighbors of a node u, D. E be the set of distinct edges in the multigraph G, and m(e) for an edge e. E be its multiplicity (i.e. |E| = e.D m(e)). We prove that max{L (n) 1, L (n) 2, L (n) 3} = | ET (n) s (G)| = d(s) v.V (d(v) - 1)!! center dot e. D m(e)!-1, where L (n) 1 = L (e) 1 /( e. D m(e)!), L (n) 2 = ((s) - 1)!! v.V\s ((v) - 2)!!, and L (n) 3 = 21-|V|+| D|. We also extend all of our results to graphs having self-loops.