Spanning eulerian subdigraphs in semicomplete digraphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2021

Spanning eulerian subdigraphs in semicomplete digraphs

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-03472923 , version 1

Citer

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⟩
31 Consultations
56 Téléchargements

Partager

Gmail Facebook X LinkedIn More