图运算与Turán型问题的统一方法：路径、循环和匹配的极值谱研究

《Canadian Journal of Mathematics》：Graph operations and a unified method for Turán-type problems on paths, cycles, and matchings

本文针对图论中路径、循环和匹配的Turán型问题、度幂和与谱极值问题，提出了一种基于Kelmans运算的统一研究框架。作者通过推广Kopylov、Erd?s–Gallai和Luo等人的经典结果，解决了Nikiforov提出的开问题，并改进了路径的谱极值结论。研究首次将Kopylov风格的分析技术引入谱图论，为多类极值问题提供了系统化解法，对化学图论和结构图论具有重要理论意义。

　　

在图论的广阔天地中，如何精确刻画禁止特定子图结构的极值图特征，一直是学者们孜孜以求的核心问题。从经典的Turán定理到Erd?s–Gallai关于路径和匹配的奠基性工作，再到Kopylov关于2-连通图中长循环的精细刻画，这一领域始终充满挑战与魅力。然而，以往研究多针对特定问题采用各异方法，缺乏统一框架，特别是在谱图论与度幂问题交叉的新兴领域，更迫切需要系统化的解决方案。

正是在这样的背景下，Ai、Lei、Ning和Shi在《Canadian Journal of Mathematics》上发表了开创性研究。他们敏锐地观察到，尽管问题形式各异——无论是传统Turán数、广义Turán数、度幂和还是谱极值问题，在路径、循环和匹配这些基本图结构的约束下，其极值图都展现出相似的结构特征。这一发现引导他们构建了名为"可行参数"的统一理论框架，为多类极值问题提供了前所未有的系统性解法。

研究团队创新性地将Kelmans运算作为核心工具，结合Kopylov的分解技术，发展出一套强有力的分析方法。通过定义满足单调性的图参数类别，他们证明了在路径禁止、循环长度限制和匹配数约束等条件下，极值图均可表示为特定团与独立集的联结结构。这一突破不仅统一了以往分散的结果，更为解决Nikiforov提出的开问题提供了关键途径。

在技术方法上，作者主要运用了Kelmans运算的两种变体——标准运算和扩展运算，通过度序列的词典序单调性保证操作收敛性。结合Kopylov的α- disintegration技术分析图的高密度核心结构，并利用谱半径的不可约矩阵理论建立参数单调性。对于2-连通图的情形，还采用了路径端点度数和的最小值估计循环长度的经典方法。

主要研究成果体现在三个核心定理：

对于2-连通且禁止长度k以上循环的图，极值图必属于K_s∨((n-k+s)K₁∪K_k-2s)形式的集合，其中s取值范围为2到?(k-1)/2?。这一结论推广并强化了Kopylov的经典循环定理。

在路径禁止问题的研究中，团队确定了连通P_k-禁止图的极值结构为W_n,k-1,s型图，成功解决了Caro和Yuster提出的度幂极值问题，并将Nikiforov关于路径谱半径的界从n≥2^4k改进到n≥3k。

对于匹配数约束的情形，研究完整刻画了M_k+1-禁止连通图的极值图族，给出了从K_2k+1到S_n,k的完整分类，为Erd?s–Gallai匹配定理提供了新的视角。

特别值得关注的是，研究首次将Kopylov风格的技术引入谱图论，解决了谱半径和符号拉普拉斯谱半径的极值问题。通过建立可行参数与弱可行参数的理论框架，作者不仅覆盖了传统的边数极值，还统一处理了谱半径、度幂和、团计数等各类参数，展现了理论的广泛适用性。

这项研究的深刻意义在于，它建立了不同极值问题之间的内在联系，揭示了极图结构的普适规律。所提出的统一方法不仅能推导已知结果，更开辟了解决其他极值问题的新途径。从化学图论中的度幂指标到网络结构中的谱特征，这一理论框架都具有重要的应用价值。未来，随着可行参数概念的进一步拓展，有望在更广泛的图论极值问题中发挥重要作用，推动结构图论与谱图论的深度融合与发展。