匹配与色临界图共存约束下的谱Turán问题研究

Research on spectral Turán problems under coexistence constraints of matching and color-critical graphs

摘要

研究了同时禁止大小为s+1的匹配M_s+1和色数为r+1的色临界图F的谱Turán问题。通过引入图的覆盖数与独立覆盖数等组合参数，建立了一个分析退化图族谱极值的理论框架。在此框架下，证明了当n充分大时，n阶{M_s+1,F}-free图的最大谱半径由完全部图G(n,r,s)达到，且该极值图是唯一的。该结果不仅将Alon和Frankl关于边极值的结果推广到谱情形，并完全刻画了匹配约束与色临界图约束共存条件下的谱极值结构。

Abstract

This paper investigates the spectral Turán problem for graphs simultaneously excluding a matching of size s+1 and a color-critical graph F with chromatic number r+1. By introducing combinatorial parameters such as the covering number and independent covering number of the graph, this paper develops a unified framework for analyzing spectral extremal problems of degenerate forbidden graph families. Based on this framework, it is proved that, for sufficiently large n, the maximum spectral radius of an n-vertex {M_s+1,F}-free graph is attained by the complete r-partite graph G(n,r,s), and this extremal graph is uniquely determined. This result not only extends the edge-extremal results of Alon and Frankl to the spectral setting, but also completely determines the spectral extremal structure under the coexistence constraints of matchings and color-critical graphs in this setting.

关键词

色临界图 / 最大谱半径 / Turán问题 / 极值图

Key words

chromatic critical graph / maximum spectral radius / Turán problem / extremal graph

作者贡献声明

王祥东提出研究问题、设计研究方案、确定理论框架，撰写初稿、修订内容、润色语言等。倪振羽提供学术指导、把握方向，对论文内容提出关键修改意见、逻辑调整，并提供经费支持。

AI使用声明

本文未使用人工智能（AI）协助撰写。

利益冲突声明

作者声明，其不存在已知的可能影响本论文所报告工作的竞争性经济利益或个人关系。

伦理声明

不适用: 本文不涉及人类或动物的生物学研究。

数据可用性

不适用。

参考文献

[1] Nikiforov V. The spectral radius of graphs without paths and cycles of specified length[J]. Linear Algebra and its Applications, 2010, 432(9): 2243-2256.

[2] Cioabă S, Desai D N, Tait M . A spectral Erdős—Sós theorem[J]. SIAM Journal on Discrete Mathematics, 2023, 37(3): 2228-2239.

[3] Fang L F, Tait M, Zhai M Q . Decomposition family and spectral extremal problems on non—bipartite graphs[J]. Discrete Mathematics, 2025, 348(10): 114527.

[4] Wang J, Kang L Y, Xue Y S . On a conjecture of spectral extremal problems[J]. Journal of Combinatorial Theory, Series B, 2023, 159: 20-41.

[5] Wang H Y, Hou X M, Ma Y . Spectral extrema of graphs with bounded clique number and matching number[J]. Linear Algebra and its Applications, 2023, 669: 125-135.

[6] Jiang S X, Yuan X Y, Zhai Y N . Some stability results for spectral extremal problems of graphs with bounded matching number[J]. Linear Algebra and its Applications, 2025, 708: 513-524.

[7] Alon N, Frankl P . Turán graphs with bounded matching number[J]. Journal of Combinatorial Theory, Series B, 2024, 165: 223-229.

[8] Hong Y. Bounds of eigenvalues of graphs[J]. Discrete Mathematics, 1993, 123(1/2/3): 65-74.

[9] Wu B F, Xiao E L, Hong Y . The spectral radius of trees on k pendant vertices[J]. Linear Algebra and its Applications, 2005, 395: 343-349.

[10] Chvátal V, Hanson D . Degrees and matchings[J]. Journal of Combinatorial Theory, Series B, 1976, 20(2): 128-138.

[11] Erdős P, Simonovits M . A limit theorem in graph theory[J]. Studia Scientiarum Mathematicarum Hungarica, 1966, 1: 51-57.