{"id":"arxiv/2609.06701","url":"https://arxiv.org/abs/2609.06701","tags":["math.CO"],"score":0,"title":"Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs","domain":"math.CO","source":"arxiv","authors":["Evangelos Bartzos","Michalis Samaris"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-06","reactions":{}}