Subeulerian Oriented Graphs

Zhenzhen Li, Baoyindureng Wu*, Anders Yeo

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

9 Downloads (Pure)

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.

OriginalsprogEngelsk
TidsskriftTaiwanese Journal of Mathematics
Vol/bind27
Udgave nummer6
Sider (fra-til)1041-1052
Antal sider12
ISSN1027-5487
DOI
StatusUdgivet - dec. 2023

Fingeraftryk

Dyk ned i forskningsemnerne om 'Subeulerian Oriented Graphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater