## 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.

Original language | English |
---|---|

Journal | Journal of Graph Theory |

Volume | 102 |

Issue number | 3 |

Pages (from-to) | 578-606 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - Mar 2023 |

## Keywords

- arc-connectivity
- eulerian subdigraph
- polynomial algorithm
- semicomplete digraph
- tournament