Skip to content
DraconiticResearch
Search Sources API
194,161 studies31 sourcesUpdated 4 min ago
PreprintarXiv licencearXiv

Two-block paths in oriented graphs under the Ore-type condition

  • Ke Zhao
  • Jia Zhou
  • Yunshu Gao
Open at sourcePDFDOICite

Abstract

Stein conjectured that for every positive integer k, every oriented graph with minimum semi-degree greater than k/2 contains every oriented path of length k [Springer Optim.Appl. 165 (2020), 459--486]. For directed paths this is a classical result of Jackson (1981). The two-block case of the conjecture was established by Chen, Hou and Zhou (2025). In this paper we prove the two-block analogue of Jackson's theorem. For all positive integers s and r, let P(s,r) be the oriented path consisting of two directed paths of lengths s and r with a common terminal vertex, and let Q(s,r) be its reverse. We show that for all K≥3 and all s,r≥1 with s+r≤ K, every oriented graph D with δ(D)≥ K and dD+(u)+dD-(v)≥ K−1 for every ordered pair of distinct vertices (u,v)∉ A(D) contains both P(s,r) and Q(s,r). Our result is the two-block analogue of Jackson's theorem, and it extends the two-block result of Chen, Hou and Zhou. The proof iterates a shift of the terminal vertex of a longest path.

Related

  1. Oriented paths with two blocks in bipartite oriented graphs
    Bin Chen, Meishuang Chen, Xinmin Hou +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Acyclic Dicolourings of Oriented Graphs: Paths, Random Tournaments, and Critical Orders
    Yihang Liu, Zhenyu Yang, Yuwan Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A New Sufficient Condition for Oriented Graphs Determined by Their Generalized Skew Spectra
    Limeng Lin, Wei Wang, Wei Wang +1
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Uniform Chebyshev approximations of functions satisfying a variation-type condition: reconstruction of time-varying signals on graphs
    Davide Bianchi, Sandra Saliani, Dimitrios Vavitsas
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsNumerical analysis & scientific computingarXiv
  5. Oriented Paths with Few Direction Flips Are Tournament Anti-Sidorenko
    Hao Chen, Yupeng Lin
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{zhao2026twoblock,
  title = {{Two-block paths in oriented graphs under the Ore-type condition}},
  author = {Ke Zhao and Jia Zhou and Yunshu Gao},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.04691},
  eprint = {2611.04691},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.04691},
}
RIS
TY  - UNPB
TI  - Two-block paths in oriented graphs under the Ore-type condition
AU  - Ke Zhao
AU  - Jia Zhou
AU  - Yunshu Gao
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.04691
UR  - https://arxiv.org/abs/2611.04691
AB  - Stein conjectured that for every positive integer k, every oriented graph with minimum semi-degree greater than k/2 contains every oriented path of length k [Springer Optim.Appl. 165 (2020), 459--486]. For directed paths this is a classical result of Jackson (1981). The two-block case of the conjecture was established by Chen, Hou and Zhou (2025). In this paper we prove the two-block analogue of Jackson's theorem. For all positive integers s and r, let P(s,r) be the oriented path consisting of two directed paths of lengths s and r with a common terminal vertex, and let Q(s,r) be its reverse. We show that for all K≥3 and all s,r≥1 with s+r≤ K, every oriented graph D with δ(D)≥ K and d_D^+(u)+d_D^-(v)≥ K−1 for every ordered pair of distinct vertices (u,v)∉ A(D) contains both P(s,r) and Q(s,r). Our result is the two-block analogue of Jackson's theorem, and it extends the two-block result of Chen, Hou and Zhou. The proof iterates a shift of the terminal vertex of a longest path.
ER  -