Spanning eulerian subdigraphs in semicomplete digraphs - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2021

Spanning eulerian subdigraphs in semicomplete digraphs

(1) , (2) , (2)
1
2

Abstract

A digraph is eulerian if it is connected and every vertex has its in-degree equal to its outdegree. Having a spanning eulerian subdigraph is thus a weakening of having a hamiltonian cycle. In this paper, we first characterize the pairs (D, a) of a semicomplete digraph D and an arc a such that D has a spanning eulerian subdigraph containing a. In particular, we show that if D is 2-arc-strong, then every arc is contained in a spanning eulerian subdigraph. We then characterize the pairs (D, a) of a semicomplete digraph D and an arc a such that D has a spanning eulerian subdigraph avoiding a. 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 f (k) such that every f (k)-arc-strong semicomplete digraph contains a spanning eulerian subdigraph avoiding any prescribed set of k arcs. We conjecture that f (k) = k + 1 and establish this conjecture for k ≤ 3 and when the k arcs that we delete form a forest of stars. A digraph D is eulerian-connected if for any two distinct vertices x, y, the digraph D has a spanning (x, y)-trail. We prove that every 2-arc-strong semicomplete digraph is eulerianconnected. All our results may be seen as arc analogues of well-known results on hamiltonian paths and cycles in semicomplete digraphs.
Fichier principal
Vignette du fichier
supereulerian-revise.pdf (398.22 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03472923 , version 1 (09-12-2021)

Identifiers

  • HAL Id : hal-03472923 , version 1

Cite

Frédéric Havet, Jørgen Bang-Jensen, Anders Yeo. Spanning eulerian subdigraphs in semicomplete digraphs. [Research Report] Inria; CNRS; I3S; Université côte d'azur. 2021. ⟨hal-03472923⟩
42 View
36 Download

Share

Gmail Facebook Twitter LinkedIn More