Spanning eulerian subdigraphs in semicomplete digraphs

DOI10.1002/JGT.22888MaRDI QIDQ6046690zbMATH OpenOpenAlexFDO

Authors Jørgen Bang-Jensen, Frédéric Havet, A. Yeo

Publication date 6 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1905.11019

zbMATH Keywords

arc-connectivityEulerian subdigraphpolynomial algorithmsemicomplete digraphtournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85)

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 $(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 prove $f(k)leq(k+1{)}^2/4+1$, conjecture $f(k)=k+1$ and establish this conjecture for $kleq3$ 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 eulerian-connected. All our results may be seen as arc analogues of well-known results on hamiltonian cycles in semicomplete digraphs.

Recommendations

• Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments
• Supereulerian digraphs with large arc-strong connectivity
• Supereulerian extended digraphs
• Supereulerian digraphs with forbidden induced subdigraphs containing short semi-paths
• Matching and spanning trails in digraphs

Cites work

• A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs
• Classes of directed graphs
• Digraphs
• Hamiltonian Cycles Avoiding Prescribed Arcs in Tournaments
• Hamiltonian dicycles avoiding prescribed arcs in tournaments
• Hamiltonian-connected tournaments
• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 3156381 (Why is no real title available?)
• scientific article; zbMATH DE number 3013308 (Why is no real title available?)
• Spanning 2-strong tournaments in 3-strong semicomplete digraphs
• Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments
• Spanning local tournaments in locally semicomplete digraphs
• Sufficient conditions for a digraph to be supereulerian
• Trail-connected tournaments

Cited in

(14)

• Spanning eulerian subgraphs, the splitting lemma, and Petersen's theorem
• Spanning Eulerian subgraphs of large size
• Symmetric core and spanning trails in directed networks
• Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments
• scientific article; zbMATH DE number 15867 (Why is no real title available?)
• scientific article; zbMATH DE number 6604940 (Why is no real title available?)
• Spanning Eulerian subdigraphs in jump digraphs
• Subeulerian oriented graphs
• Symmetric cores and extremal size bound for supereulerian semicomplete bipartite digraphs
• Strong arc decompositions of split digraphs
• Hamiltonian cycles avoiding prescribed arcs in semicomplete digraphs
• Hamiltonian cycles avoiding a spanning forest or a spanning cycle subgraph in tournaments
• A proof to Bang-Jensen, Havet and Yeo's conjecture on the Hamiltonian cycles avoiding prescribed arcs in semicomplete digraphs
• Edge-arc-disjoint paths in semicomplete mixed graphs

This page was built for publication: Spanning eulerian subdigraphs in semicomplete digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046690)