## Abstract

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.

Originalsprog | Engelsk |
---|---|

Tidsskrift | Taiwanese Journal of Mathematics |

Vol/bind | 27 |

Udgave nummer | 6 |

Sider (fra-til) | 1041-1052 |

Antal sider | 12 |

ISSN | 1027-5487 |

DOI | |

Status | Udgivet - dec. 2023 |