Spanning eulerian subdigraphs in semicomplete digraphs

Jørgen Bang-Jensen, Frédéric Havet*, Anders Yeo

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

33 Downloads (Pure)

Abstract

A digraph is eulerian if it is connected and every vertex has its in-degree equal to its out-degree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. In this paper, we first characterize the pairs (Formula presented.) of a semicomplete digraph (Formula presented.) and an arc (Formula presented.) such that (Formula presented.) has a spanning eulerian subdigraph containing (Formula presented.). In particular, we show that if (Formula presented.) is 2-arc-strong, then every arc is contained in a spanning eulerian subdigraph. We then characterize the pairs (Formula presented.) of a semicomplete digraph (Formula presented.) and an arc (Formula presented.) such that (Formula presented.) has a spanning eulerian subdigraph avoiding (Formula presented.). In particular, we prove that every 2-arc-strong semicomplete digraph has a spanning eulerian subdigraph avoiding any prescribed arc. We also prove the existence of a (minimum) function (Formula presented.) such that every (Formula presented.) -arc-strong semicomplete digraph contains a spanning eulerian subdigraph avoiding any prescribed set of (Formula presented.) arcs. We conjecture that (Formula presented.) and establish this conjecture for (Formula presented.) and when the (Formula presented.) arcs that we delete form a forest of stars. A digraph (Formula presented.) is eulerian-connected if for any two distinct vertices (Formula presented.), the digraph (Formula presented.) has a spanning (Formula presented.) -trail. We prove that every 2-arc-strong semicomplete digraph is eulerian-connected. All our results may be seen as arc analogues of well-known results on hamiltonian paths and cycles in semicomplete digraphs.

OriginalsprogEngelsk
TidsskriftJournal of Graph Theory
Vol/bind102
Udgave nummer3
Sider (fra-til)578-606
ISSN0364-9024
DOI
StatusUdgivet - mar. 2023

Bibliografisk note

Funding Information:
We are grateful to the referees for their comments that helped improving our paper. This study was supported by the Danish research council under grant number DFF 7014‐00037B, by the DISCO project, PICS, CNRS, and by the french Agence Nationale de la Recherche under contract Digraphs ANR‐19‐CE48‐0013‐01.

Publisher Copyright:
© 2022 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Spanning eulerian subdigraphs in semicomplete digraphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater