Skip to content
#edge computing Preprint

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

Sep 2026 · 1 citation · 23 references
Mathematics

TL;DR

The bounds on the number of Eulerian orientations for certain classes of connected, loopless $4-regular graphs are improved and a divide-and-conquer algorithm is provided that leverages structural properties to compute the exact number of Eulerian orientations for separable graphs without exhaustive enumeration.

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 \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 F.Bories et.al. (1983) for simple graphs and by G.Ding et.al. (2003) for multigraphs, on the number of Eulerian orientations.

View source

Similar papers

Preprint Aug 2026

The Cayley Completion of a Graph

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completi...

Rigobert Fokam Souop, Laurent Bitjoka · 2 citations · ⚡2
Preprint Sep 2026

Connected Mutual-Visibility in Graphs

A set $S$ of vertices of a graph $G$ is a connected mutual-visibility set if every two vertices of $S$ are joined by a shortest path whose internal vertices lie outside $S$, and the subgraph induced by $S$ is connected. We introduce the connected mutual-visibility number $\mu_c(G)$, defined as the maximum cardinality o...

B. TonnyK, M. Shikhi · 0 citations
Preprint Aug 2026

A Tight Bound for Facial Distance Patterns in Planar Graphs

There is currently a gap between the time for computing the diameter between weighted and unweighted planar graphs, and a (centralized) $\tilde{O}(n^{8/5})$-time algorithm for computing the diameter is presented, improving over the $\tilde{O}(n^{5/3})$ algorithm of [SODA'18] which works for weighted directed planar gra...

Viktor Fredslund-Hansen, S. Mozes, Oren Weimann · 0 citations
Preprint Aug 2026

Rigidity of expanders and pseudorandom graphs

A graph $G=(V,E)$ is called $d$-rigid if, for a generic embedding of its vertices in $\mathbb{R}^d$, the only continuous motions of the vertices preserving the distances between all pairs of adjacent vertices are those induced from the isometries of $\mathbb{R}^d$ (that is, translations and rotations of the whole graph...

Michael Krivelevich, Alan Lew, Peleg Michaeli · 0 citations
Preprint Aug 2026

Disconnected graphs and extremal bounds for realizable distance orders

Let $G$ be a graph together with a total order $\prec$ on its edges. We say that $\prec$ is realizable in $\mathbb{R}^d$ if there is a placement of the vertices of $G$ in $\mathbb{R}^d$ such that the Euclidean lengths of the edges induce exactly the order $\prec$. Almendra-Hern\'andez and Mart\'inez-Sandoval proved tha...

Gerardo L. Maldonado, Leonardo Martínez-Sandoval, Miguel Raggi et al. · 0 citations
Preprint Sep 2026

On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts

Let $G$ be a $3$-partite graph with $k$ vertices in each part such that the bipartite graph induced by any two parts contains no cycle of length four. Fischer and Matou\v{s}ek [J. Combin. Theory Ser. A, 2001] asked for the maximum number of triangles in such a graph. They obtained the lower bound $(1-o(1))k^{3/2}$ and...

Chun-Qiu Fang, Rong-Xing Xu · 1 citation

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Oct 29, 2026

Microsoft Research Focus – Edition #97

Host Sowbhagya Suresh shares some of the latest news and cutting-edge research from across Microsoft—from understanding the challenges facing coding agents to uncovering how people use AI at work and improving extended-range weather forecasting. The post Microsoft Research Focus – Edition #97 appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.