Cycles of Lengths 3 and $$n-1$$ in Digraphs Under a Bang-Jensen–Gutin–Li Type Condition
Graphs and Combinatorics · 2026-04 · 42 (2)
DOI: 10.1007/s00373-026-03022-y ↗Kurz gefasst
Fachartikel in der Zeitschrift Graphs and Combinatorics, online erschienen am 19.02.2026. Verfasst von Zan-Bo Zhang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 14 Literaturangaben. Gefördert von: Basic and Applied Basic Research Foundation of Guangdong Province, National Natural Science Foundation of China.
Abstract (Originalsprache)
Bang-Jensen–Gutin–Li type conditions are the conditions for hamiltonicity of digraphs which impose degree restrictions on non-adjacent vertices which have a common in-neighbor or a common out-neighbor. They can be viewed as an extension of Fan type conditions in undirected graphs, as well as generalization of locally (in-, out-)semicomplete digraphs. Since their first appearance in 1996, various Bang-Jensen–Gutin–Li type conditions for hamiltonicity have come forth. However, no such conditions for pancyclicity appear in the literature. In this paper, we identify an obstacle to generalize the original condition to pancyclicity, and propose a conjecture on a pancyclicity condition derived through an appropriate strengthening of the original one. Let D be a strong digraph with order n≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 3$$\end{document}. We conjecture that, if for every u∈V(D)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u\in V(D)$$\end{document} belonging to a dominated non-adjacent pair or a dominating non-adjacent pair, we have d(u)≥n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$d(u)\ge n$$\end{document}, then D is pancyclic, unless D belongs to one of two well-characterized classes of exceptional digraphs. As a support for this conjecture, we prove that the condition in the conjecture implies the existence of a 3-cycle and an (n-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n-1)$$\end{document}-cycle in D, unless D belongs to the completely characterized classes of exceptional digraphs.
Förderung
- Basic and Applied Basic Research Foundation of Guangdong Province
- National Natural Science Foundation of China
Zitieren
APA
Zhang, Z., Wu, W., He, W., & Li, T. (2026). Cycles of Lengths 3 and $$n-1$$ in Digraphs Under a Bang-Jensen–Gutin–Li Type Condition. Graphs and Combinatorics, 42(2). https://doi.org/10.1007/s00373-026-03022-y
Vancouver
Zhang Z, Wu W, He W, Li T. Cycles of Lengths 3 and $$n-1$$ in Digraphs Under a Bang-Jensen–Gutin–Li Type Condition. Graphs and Combinatorics. 2026;42(2). doi:10.1007/s00373-026-03022-y
BibTeX
@article{Zhang2026,
author = {Zhang, Zan-Bo and Wu, Wenhao and He, Weihua and Li, Tianyue},
title = {Cycles of Lengths 3 and $$n-1$$ in Digraphs Under a Bang-Jensen–Gutin–Li Type Condition},
journal = {Graphs and Combinatorics},
year = {2026},
volume = {42},
number = {2},
doi = {10.1007/s00373-026-03022-y}
}
EUVIMED