Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.06701
curl -X POST /api/v1/records/arxiv/2609.06701/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.06701/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'