Metraipolis › archive › dc_7a36a52da725
Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs — arXiv:2609.06701
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.06701
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T14:48:37.177Z
- SHA-256 of the archived text
a8a6cddb77e264b79dd2fde545cdd853753cbe54a52d6809d2493aaf8f9b8edb- Stable URL of this page
https://metraipolis.com/documento/dc_7a36a52da725
How to cite
Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs — arXiv:2609.06701 — arXiv (en), https://arxiv.org/abs/2609.06701 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7a36a52da725 (Metraipolis archive dc_7a36a52da725, sha256 a8a6cddb77e264b79dd2fde545cdd853753cbe54a52d6809d2493aaf8f9b8edb)
BibTeX
@misc{dc7a36a52da725,
title = {Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs — arXiv:2609.06701},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.06701},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7a36a52da725; sha256 a8a6cddb77e264b79dd2fde545cdd853753cbe54a52d6809d2493aaf8f9b8edb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06701. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
An Eulerian orientation of a $4$-regular undirected graph (simple or multigraph) $G=(V,E)$ with $n=|V|$ vertices is an assignment of directions to its edges such that every vertex $v \in V$ has the same indegree and outdegree. In the present article, we improve the bounds on the number of Eulerian orientations for certain classes of connected, loopless $4$-regular graphs. The previous bound is due to M. Las Vergnas (1983) and is exactly $9\cdot 2^{n-3}$, which is a sharp bound for a certain family of multigraphs with $n\geq 4$. Here, we show that the number of Eulerian orientations for all biconnected $4$-regular multigraphs is at most $2^n+2$, which is also sharp. We exhibit families of graphs that attain this maximum value. For simple graphs, we prove an upper bound of $\mathcal{O}(3^{n/2})$ in the biconnected case and $\mathcal{O}(6^{n/3})$ for the separable case. Additionally, we provide a divide-and-conquer algorithm that leverages structural properties to compute the exact number of Eulerian orientations for separable graphs without exhaustive enumeration. Finally, we analyze the effect of standard inductive construction operations, used to generate $4$-regular graphs from smaller ones, as shown by this http URL this http URL . (1983) for simple graphs and by this http URL this http URL . (2003) for multigraphs, on the number of Eulerian orientations.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.06701 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:32:29.796Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).