Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs

Abstract

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 ∈ 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· 2ⁿ⁻³, which is a sharp bound for a certain family of multigraphs with n≥ 4. Here, we show that the number of Eulerian orientations for all biconnected $4$-regular multigraphs is at most 2ⁿ+2, which is also sharp. We exhibit families of graphs that attain this maximum value. For simple graphs, we prove an upper bound of 𝒪(3^n/2) in the biconnected case and 𝒪(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 F.Bories et.al. (1983) for simple graphs and by G.Ding et.al. (2003) for multigraphs, on the number of Eulerian orientations.

A tree bijection for Eulerian orientations on quartic maps
Marie Albenque, Enrica Duchi, Juliette Schabanel
HAL24 Jul 2026PreprintLicence not statedCombinatorics & discrete mathematicsHAL
On the Cohomology Classes of Certain Eisenstein-Kronecker Forms
Zhixuan Sheng, Jie Zhou
arXiv9 Oct 2026PreprintarXiv licenceFull textAlgebra & number theory Analysis & PDEsarXiv
On certain classes of commutative g-dimonoids
Volodymyr Gavrylkiv, Inna Hlushak, Kateryna Koporkh +2
arXiv29 Sep 2026PreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv
On the Structure of the Cut Locus in Certain Classes of Warped Product Manifolds
Nathaphon Boonnam
arXiv11 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
On the identification of certain classes of gap-rich sets
Jake Fillman, Yi-Sheng Lim
arXiv17 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeX RIS

BibTeX

@misc{bartzos2026computing,
  title = {{Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs}},
  author = {Evangelos Bartzos and Michalis Samaris},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.06701},
  eprint = {2609.06701},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.06701},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs
AU  - Evangelos Bartzos
AU  - Michalis Samaris
PY  - 2026
DA  - 2026/09/06
PB  - arXiv
DO  - 10.48550/arxiv.2609.06701
UR  - https://arxiv.org/abs/2609.06701
AB  - 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 ∈ 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· 2^n−3, which is a sharp bound for a certain family of multigraphs with n≥ 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 𝒪(3^n/2) in the biconnected case and 𝒪(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 F.Bories et.al. (1983) for simple graphs and by G.Ding et.al. (2003) for multigraphs, on the number of Eulerian orientations.
ER  -

Abstract

Related

Cite