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

Evangelos Bartzos, Michalis Samaris

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…