Subeulerian Oriented Graphs
Zhenzhen Li, Baoyindureng Wu, Anders Yeo · Taiwanese Journal of Mathematics · 2023
A graph is subeulerian if it is a spanning subgraph of an eulerian graph. All subeulerian graphs were characterized by Boesch, Suffel, Tindell in 1977. Later, a simple proof of their theorem was given by Jaeger. A digraph $D$ is eulerian if and only if $D$ is connected and $d^{+}(x) = d^{-}(x)$ for every vertex $x \in V(D)$. An orientation $\overrightarrow{G}$ of a graph $G$ is a digraph obtained from $G$ by replacing each edge $xy$ of $G$ with an arc $xy$ or $yx$. An oriented graph is an orientation of a simple graph. An oriented graph is said to be subeulerian if it is a spanning subdigraph of an eulerian oriented graph. In this paper, we initiated the study of subeulerian oriented graphs. We give a necessary and sufficient condition for an orientated digraph to be subeulerian. We refine this condition in order to give necessary and sufficient condition for an orientation of a forest to be subeulerian. Furthermore, we prove that if $G$ is a graph of order $n$ with $n \geq \max \{ 4\Delta(G)-1, 3 \}$, then every orientation of $G$ is subeulerian. In particular, we show that if $G$ is a graph of odd order $n$ with $\Delta(G) \leq n/4$, then every orientation of $G$ is a spanning subdigraph of a regular tournament.