Abstract
Given an undirected multigraph \(G=(V,E)\) with no self-loops, and one of its nodes \(s\in V\) of degree d(s), 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)\): \( 2^{1-|V|+|E|} \le |ET^{(e)}_{s}(G)| \le d(s) \, 2^{|E| \log _2 \left( \frac{|E|}{|V|}\right) + \frac{|V|}{2}}\).
We also consider the notion of node-distinct Eulerian tours. Indeed, the classical Eulerian tours are edge-distinct sequences. Node-distinct Eulerian tours should instead be different as node sequences. Letting \(ET^{(n)}_s(G)\) denote the set of node-distinct Eulerian tours in G, we show \(2^{1-|V|+\frac{1}{2}\sum _{u \in V}\varDelta (u)}\!\le \! |ET^{(n)}_{s}(G)|\!\le \! d(s) 2^{|E| \log _2 \left( \frac{|E|}{|V|}\right) + \frac{|V|}{2}}\cdot \textstyle \prod _{e\in D} m(e)!^{-1}\) where \(\varDelta (u)\) is the number of distinct neighbors of node u, \(D \subseteq E\) is the set of distinct edges in the multigraph G, and m(e) for an edge \(e\in E\) denotes its multiplicity (i.e. \(|E|=\sum _{e \in D} m(e)\)).
Student work partially supported by the Italian MIUR project AHeAD.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
It is easy to see by induction that \(k!!\ge 2^{(k-1)/2}\) for all \(k\ge 1\), and since G is Eulerian, \(d(v) \ge 2\) for all \(v\in V\).
- 2.
By a simple induction, we have \((k-1)!! \ge \exp (\frac{k-1}{2})\) for all \(k\ge 3\).
References
van Aardenne-Ehrenfest, T., de Bruijn, N.G.: Circuits and trees in oriented linear graphs. In: Classic Papers in Combinatorics, pp. 149–163. Birkhäuser Boston, Boston (1987). https://doi.org/10.1007/978-0-8176-4842-8_12
Bent, S.W., Manber, U.: On non-intersecting Eulerian circuits. Discret. Appl. Math. 18(1), 87–94 (1987)
Bernardini, G., Chen, H., Fici, G., Loukides, G., Pissis, S.P.: Reverse-safe data structures for text indexing. In: Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020, Salt Lake City, UT, USA, 5–6 January 2020, pp. 199–213 (2020)
Brightwell, G.R., Winkler, P.: Counting Eulerian circuits is #P-complete. In: ALENEX/ANALCO, pp. 259–262. ACM SIAM (2005)
Conte, A., Grossi, R., Loukides, G., Pisanti, N., Pissis, S.P., Punzi, G.: Beyond the BEST theorem: fast assessment of Eulerian trails. In: Bampis, E., Pagourtzis, A. (eds.) FCT 2021. LNCS, vol. 12867, pp. 162–175. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-86593-1_11
Creed, P.J.: Counting and sampling problems on Eulerian graphs. Ph.D. thesis, University of Edinburgh (2010)
Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae 8, 128–140 (1736)
Fleischner, H.: (Some of) the many uses of Eulerian graphs in graph theory (plus some applications). Discret. Math. 230(1), 23–43 (2001)
Ge, Q., Štefankovič, D.: The complexity of counting Eulerian tours in 4-regular graphs. Algorithmica 63(3), 588–601 (2012)
Hierholzer, C., Wiener, C.: Über die möglichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren. Math. Ann. 6(1), 30–32 (1873)
Las Vergnas, M.: Le polynôme de Martin d’un graphe Eulerien. In: Berge, C., Bresson, D., Camion, P., Maurras, J., Sterboul, F. (eds.) Combinatorial Mathematics, North-Holland Mathematics Studies, vol. 75, pp. 397–411. North-Holland (1983)
Las Vergnas, M.: An upper bound for the number of Eulerian orientations of a regular graph. Combinatorica 10(1), 61–65 (1990)
Mihail, M., Winkler, P.: On the number of Eulerian orientations of a graph. Algorithmica 16(4/5), 402–414 (1996)
Pevzner, P.A., Tang, H., Waterman, M.S.: An Eulerian path approach to DNA fragment assembly. Proc. Natl. Acad. Sci. 98(17), 9748–9753 (2001)
Punzi, G.: Novel algorithms for assessing the number of solutions in graph problems. Ph.D. thesis, University of Pisa (2023)
Schrijver, A.: Bounds on the number of Eulerian orientations. Combinatorica 3(3), 375–380 (1983)
Sohn, J.I., Nam, J.W.: The present and future of de novo whole-genome assembly. Brief. Bioinform. 19(1), 23–40 (2018)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Punzi, G. (2022). Bounding the Number of Eulerian Tours in Undirected Graphs. In: Zhang, Y., Miao, D., Möhring, R. (eds) Computing and Combinatorics. COCOON 2022. Lecture Notes in Computer Science, vol 13595. Springer, Cham. https://doi.org/10.1007/978-3-031-22105-7_33
Download citation
DOI: https://doi.org/10.1007/978-3-031-22105-7_33
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22104-0
Online ISBN: 978-3-031-22105-7
eBook Packages: Computer ScienceComputer Science (R0)