半度条件下有向图的哈密顿平方

《Discrete Applied Mathematics》：Hamiltonian squares in digraphs under semi-degree conditions

　　

摘要

本文研究在有向图中半度条件下方Hamilton圈的平方。受DeBiasio等人[Combin. Probab. Comput. 35 (2026)]问题的启发，我们证明：对任意γ>0，每个满足δ?(D)≥3/4+γn的充分大的n顶点有向图D都包含Hamilton圈的平方。这为DeBiasio等人提出的问题在k=2情形下提供了部分解答，并可视为经典图论定理在有向图上的推广。DeBiasio等人的总度定理立即给出半度界4n/5+o(n)，而我们的结果将这一界改进为3n/4+o(n)。

引言

在有向图中研究Hamilton性是一个核心问题。Faudree等人的经典定理[11]指出，对任意ε>0，存在常数c=c(ε)，使得每个满足最小度δ(G)≥3/4+εn+c的n顶点图G都包含Hamilton圈的平方。这个结果是无向图中Pósa-Seymour猜想的解决过程中的重要一步。

在有向图中，情况更加复杂。即使在有向简单图中研究基本Hamilton圈，确定正确的半度阈值也是一个长期存在的问题，直到Keevash等人[15]证明δ?(D)≥(3n-4)/8对大型有向简单图是充分且最优的。关于有向图和有向简单图中Hamilton圈的背景，参见综述[19]。

对于有向图和有向简单图中Hamilton圈的幂次，直到最近了解甚少。对于有向完全图，Dragani?等人[5]证明了Hamilton圈第k次幂存在的最小半度阈值的紧致界为δ?(T)≥n/4+cn^(1-1/?k/2?)。从有向完全图到有向简单图，DeBiasio等人[3]证明最小半度条件δ?(D)≥(1/2-1/(106000k))n足以保证充分大的有向简单图D包含Hamilton圈的第k次幂。

对于一般有向图，在同一篇论文[3]中，他们还取得了重大突破，渐近确定了强制Hamilton圈平方的最小总度阈值。具体地，对任意η>0，每个满足δ(D)≥8/5+ηn的充分大的n顶点有向图D都包含Hamilton圈的平方。由于δ(D)≥2δ?(D)，此结果立即蕴含：对任意ε>0，条件δ?(D)≥(4/5+ε)n是充分的。

与圈的平方紧密相关的是圈的反向平方。对于圈C，其反向平方是具有相同顶点集的有向图，其弧集为C的所有弧和所有满足C中从x到y的有向距离恰好为2的弧yx的并集。Zhang等人[24]证明每个满足δ?(D)≥2/3+γn的充分大有向图D都包含Hamilton圈的反向平方。尽管反向平方和平方共享相同的Hamilton骨干，但后者更具限制性，因为距离为2的弧必须沿着底层循环顺序全部一致地向前定向。

相比之下，确定一般有向图中Hamilton圈平方的最小半度条件似乎是一个困难得多的问题。这一问题最初由Treglown[23]提出，后由DeBiasio等人[3]正式化为以下仍然开放的问题，即使在k=2的情形下也是如此。

问题1.1 [3] 每个满足δ?(D)≥k/(k+1)n的n顶点有向图D是否包含Hamilton圈的第k次幂？

本文在k=2情形下对问题1.1取得进展，证明了以下渐近结果。

定理1.2 对任意γ>0，存在n?∈?，使得对任意n≥n?，以下结论成立。设D是满足δ?(D)≥3/4+γn的n顶点有向图，则D包含Hamilton圈的平方。

DeBiasio等人的总度定理[3]给出了4n/5的渐近充分半度界，而定理1.2将这一界改进为3n/4。我们的结果也可视为无向图中Faudree等人经典定理在有向图上的推广。

定理1.3 [11] 对任意ε>0，存在常数c=c(ε)，使得每个满足δ(G)≥3/4+εn+c的n顶点图G都包含Hamilton圈的平方。

作为定理1.2的进一步推论，我们导出以下因子定理。此处C?2表示?顶点圈的平方，C?2-因子指由两两顶点不相交的C?2副本组成的生成子图。

推论1.4 对任意γ>0，存在??=??(γ)，使得对任意?≥??和任意正整数m，每个满足最小半度δ?(D)≥3/4+γ·m的m顶点有向图D都包含C?2-因子。

论文结构。本文结构如下。第2节引入必要记号、概率工具和证明策略概述。第3节建立近乎覆盖、吸收和连接引理。第4节结合这些要素证明定理1.2，并由此推导推论1.4。

第3节摘要

记号

本文未定义的记号参见[1]。全文中所有有向图均为有限无环的。对有向图D，记V(D)和A(D)分别为其顶点集和弧集，|D|=|V(D)|。给定正整数t，记[t]={1,...,t}。集合X的基数记为|X|。若X?V(D)，则D[X]表示D中由X诱导的子图，记D-X=D[V(D)\X]。更一般地，若H是D的子图，则D-H=D[V(D)\V(H)]。

近似覆盖引理

我们将使用DeBiasio等人[3]中的引理5.2。

引理3.1 [3] 对任意整数k≥2和η>0，存在n?,T∈?，使得对任意n≥n?，若n顶点有向图G满足δ(G)≥2(1-1/(k+2)+η)n，则G包含至多T条两两顶点不相交的k-路径，覆盖所有但至多ηn个顶点。

由于δ(D)≥2δ?(D)，由此立即得到以下最小半度版本。

引理3.2 近似覆盖引理 对任意整数k≥2和实数γ>0，存在n?=n?(k,γ)∈?和T=T(k,γ)∈?，使得对任意...

定理1.2的证明

选取常数η,ξ>0和n?,T∈?，使得0<1/n??1/T?η?ξ?γ<1。

设n≥n?，D是满足δ?(D)≥3/4+γn的n顶点有向图。

我们将定理1.2的证明分为四步，如第2.2节所述。

第一步：构造吸收2-路径。

我们首先在D中构造一条2-路径PA，其初始弧和终止弧分别记为x?y?和u?v?，满足以下性质：

(i) |V(PA)|≤η/2·n；

(ii) 对任意集合L?V(D\PA)满足|L|≤η/4·n，有向图D[L∪V(PA)]包含一条生成2-路径。

结束语

本文证明了：对任意γ>0，每个满足δ?(D)≥(3/4+γ)n的充分大的n顶点有向图D都包含Hamilton圈的平方。DeBiasio等人的最小总度结果[3]给出4n/5的渐近充分半度界，而我们的结果将这一界降低到3n/4。我们的定理也可视为Faudree等人经典结果在有向图上的推广，并给出了[3]中所提问题在k=2情形下的部分解答。

致谢

作者感谢审稿人提出的宝贵意见和建议。

作者：王芝兰 | 魏硕 | 严进