Note on Long Paths in Eulerian Digraphs
Copyright policy )Note on Long Paths in Eulerian Digraphs
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 [Knierim, Larcher, Martinsson, Noever, JCTB 148:125--148] 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.
- ETH Zurich Switzerland
Extremal problems in graph theory, Eulerian and Hamiltonian graphs, Hajós conjecture, Distance in graphs, FOS: Mathematics, Directed graphs (digraphs), tournaments, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, minimum number of paths
Extremal problems in graph theory, Eulerian and Hamiltonian graphs, Hajós conjecture, Distance in graphs, FOS: Mathematics, Directed graphs (digraphs), tournaments, Mathematics - Combinatorics, Combinatorics (math.CO), Paths and cycles, minimum number of paths
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!