Subeulerian Oriented Graphs

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 ∈ V (D). An orientation −→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 ≥ max{4∆(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 ∆(G) ≤ n/4, then every orientation of G is a spanning subdigraph of a regular tournament.