EUVIMEDEUVIMED entdecken
Crossref

Long antipaths and anticycles in oriented graphs

Bin Chen, Xinmin Hou, Xinyu Zhou

Discrete Mathematics · 2025-05 · 348 (5) · 114412

DOI: 10.1016/j.disc.2025.114412 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics, 2025-05. Verfasst von Bin Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 18 Literaturangaben. Gefördert von: National Key Research and Development Program of China, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let $\delta^{0}(D)$ be the minimum semi-degree of an oriented graph $D$. Jackson (1981) proved that every oriented graph $D$ with $\delta^{0}(D)\geq k$ contains a directed path of length $2k$ when $|V(D)|>2k+2$, and a directed Hamilton cycle when $|V(D)|\le 2k+2$. Stein~(2020) further conjectured that every oriented graph $D$ with $\delta^{0}(D)>k/2$ contains any orientated path of length $k$. Recently, Klimo\u{s}ov\'{a} and Stein (DM, 2023) introduced the minimum pseudo-semi-degree $\tilde\delta^0(D)$ (a slight weaker than the minimum semi-degree condition as $\tilde\delta^0(D)\ge \delta^0(D))$ and showed that every oriented graph $D$ with $\tilde\delta^{0}(D)\ge (3k-2)/4$ contains each antipath of length $k$ for $k\geq 3$. In this paper, we improve the result of Klimo\u{s}ov\'{a} and Stein by showing that for all $k\geq 2$, every oriented graph with $\tilde\delta^0(D)\ge(2k+1)/3$ contains either an antipath of length at least $k+1$ or an anticycle of length at least $k+1$. Furthermore, we answer a problem raised by Klimo\u{s}ov\'{a} and Stein in the negative.

Förderung

  • National Key Research and Development Program of China
  • National Natural Science Foundation of China

Zitieren

APA

Chen, B., Hou, X., & Zhou, X. (2025). Long antipaths and anticycles in oriented graphs. Discrete Mathematics, 348(5), 114412. https://doi.org/10.1016/j.disc.2025.114412

Vancouver

Chen B, Hou X, Zhou X. Long antipaths and anticycles in oriented graphs. Discrete Mathematics. 2025;348(5):114412. doi:10.1016/j.disc.2025.114412

BibTeX
@article{Chen2025,
  author = {Chen, Bin and Hou, Xinmin and Zhou, Xinyu},
  title = {Long antipaths and anticycles in oriented graphs},
  journal = {Discrete Mathematics},
  year = {2025},
  volume = {348},
  number = {5},
  pages = {114412},
  doi = {10.1016/j.disc.2025.114412}
}
Kostenlos starten →