四边形无关图的最多边数问题
The Problem of Maximal Edge Number of Quadrilateral-Free Graph
DOI: 10.12677/aam.2025.1410419, PDF,    国家自然科学基金支持
作者: 崔超凡*：宁夏师范大学数学与计算机科学学院，宁夏 固原；晁福刚#：商洛学院数学与计算机应用学院，陕西 商洛
关键词: 极值图论；四边形无关图；Extremal Graph Theory； C4-Free Graph
摘要: 本文研究了极值图论中的一个特定问题：在一个含10个顶点的图中，当其无4–圈但必须包含至少一个三角形时，其边数的最大值是多少？通过分析相关极值图的性质并结合构造性证明，确定了该问题的精确值为14。此结果揭示了小规模极值图的结构“刚性”，即一个局部结构约束(必须存在c3)的引入，如何显著地将其全局边数上限从16降低至14。
Abstract: This paper investigates a specific problem in extremal graph theory: determining the maximum number of edges in a graph on 10 vertices that is 4-cycle-free but is required to contain at least one triangle. By analyzing the properties of related extremal graphs and providing a constructive proof, we establish that the exact value of this maximum is 14. This result reveals the structural rigidity of small-scale extremal graphs, demonstrating how the imposition of a local constraint, the mandatory presence of a c3 significantly reduces the graph’s global edge limit from 16 to 14.
文章引用：崔超凡, 晁福刚. 四边形无关图的最多边数问题[J]. 应用数学进展, 2025, 14(10): 62-69. https://doi.org/10.12677/aam.2025.1410419

参考文献

[1] Mantel, W. (1907) Problem 28. Wiskundige Opgaven, 10, 60-61.
[2] Turán, P. (1941) On an Extremal Problem in Graph Theory. Matematikai és Fizikai Lapok, 48, 436-452.
[3] Erdös, P. and Stone, A.H. (1946) On the Structure of Linear Graphs. Bulletin of the American Mathematical Society, 52, 1087-1091. [Google Scholar] [CrossRef] 
[4] Zarankiewicz, K. (1951) Problem P 101. Colloquium Mathematicum, 2, 301.
[5] Kóvari, T., Sós, V. and Turán, P. (1954) On a Problem of K. Zarankiewicz. Colloquium Mathematicum, 3, 50-57. [Google Scholar] [CrossRef] 
[6] Bondy, J.A. (1995) Extremal Problems of Graph Theory. In: Graham, R.L., Grötschel, M. and Lovász, L., Eds., Handbook of Combinatorics, Vol. 1, Elsevier, 499-557.
[7] Erdős, P., Rényi, A. and Sós, V.T. (1966) On a Problem of Graph Theory. Studia Scientiarum Mathematicarum Hungarica, 1, 215-235.
[8] Clapham, C.R.J., Flockhart, A. and Sheehan, J. (1989) Graphs without Four‐Cycles. Journal of Graph Theory, 13, 29-47. [Google Scholar] [CrossRef] 
[9] Garnick, D.K., Kwong, Y.H.H. and Lazebnik, F. (1993) Extremal Graphs of Girth 5. Journal of Graph Theory, 17, 633-647.
[10] Simonovits, M. (1968) A Method for Solving Extremal Problems in Graph Theory, Stability Problems. In: Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, 279-319.
[11] Brown, W.G. (1966) On Graphs That Do Not Contain a Thomsen Graph. Canadian Mathematical Bulletin, 9, 281-285. [Google Scholar] [CrossRef] 

为你推荐