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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$n\ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. We conjecture that, if for every <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$u\in V(D)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> belonging to a dominated non-adjacent pair or a dominating non-adjacent pair, we have <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$d(u)\ge n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, 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 <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$(n-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-cycle in D, unless D belongs to the completely characterized classes of exceptional digraphs.

Cycles of Lengths 3 and $n-1$ in Digraphs Under a Bang-Jensen–Gutin–Li Type Condition

期刊论文
发表日期：

2026年2月19日

查看全文

Zan-Bo Zhang,
Wenhao Wu,
Weihua He,
Tianyue Li

摘要

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\ge 3$ $n \geq 3$ . We conjecture that, if for every $u\in V(D)$ $u \in V (D)$ belonging to a dominated non-adjacent pair or a dominating non-adjacent pair, we have $d(u)\ge n$ $d (u) \geq n$ , 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)$ $(n - 1)$ -cycle in D, unless D belongs to the completely characterized classes of exceptional digraphs.

Cycles of Lengths 3 and \(n-1\) in Digraphs Under a Bang-Jensen–Gutin–Li Type Condition

摘要