Note on long paths in Eulerian digraphs

DOI10.37236/10297MaRDI QIDQ2034059zbMATH OpenOpenAlexFDO

Authors Charlotte Knierim, Maxime Larcher, Anders Martinsson

Publication date 21 June 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Hajós conjectureminimum number of paths

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Abstract: Long Paths and Cycles in eulerian digraphs have gotten a lot of attention recently. In this short note, we show how to use methods from Knierim, Larcher, Martinsson, Noever (2021) to find paths of length $d/(logd+1)$ in Eulerian digraphs with average degree $d$, improving the recent result of $Omega(d^{1/2+1/40})$. Our result is optimal up to at most a logarithmic factor.

Review text

Summary: Long paths and cycles in Eulerian digraphs have received a lot of attention recently. In this short note, we show how to use methods from [\textit{C. Knierim} et al., J. Comb. Theory, Ser. B 148, 125--148 (2021; Zbl 07318560)] to find paths of length \(d/(\log d+1)\) in Eulerian digraphs with average degree \(d\), improving the recent result of \(\Omega(d^{1/2+1/40})\). Our result is optimal up to at most a logarithmic factor.

Recommendations

• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• Diameter and maximum degree in Eulerian digraphs
• Finding Long Paths, Cycles and Circuits
• Automata, Languages and Programming
• scientific article; zbMATH DE number 3946164

Cites work

• A proof of a conjecture of Bondy concerning paths in weighted digraphs
• Introduction to algorithms.
• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• Long cycles, heavy cycles and cycle decompositions in digraphs
• On maximal paths and circuits of graphs

Cited in

(2)

• Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs
• Towards Graham's rearrangement conjecture via rainbow paths

This page was built for publication: Note on long paths in Eulerian digraphs

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