期刊目次

加入编委

期刊订阅

添加您的邮件地址以接收即将发行期刊数据:

Open Access Article

Advances in International Applied Mathematics. 2025; 7: (2) ; 1-7 ; DOI: 10.12208/j.aam.20250010.

Generalized Turán problems for a matching and an even cycle
关于匹配和偶圈的广义 Turán问题

作者: 任荣杰 *

南京航空航天大学数学学院 江苏南京

*通讯作者: 任荣杰,单位:南京航空航天大学数学学院 江苏南京;

发布时间: 2025-06-20 总浏览量: 10

摘要

Turán数是极值图论的经典研究问题。星图 是由两个点集构成的一个完全二部图,其满足:一个集合只有一个顶点,另一个集合有 个顶点。设 是一个图集合。广义Turán数 表示在一个具有 个顶点且不包含 中任意图为子图的图中,所含星图 的最大个数。我们用 , 分别表示具有 条边的匹配和 条边的圈。在本文中,利用星图的结构性质和组合数的凸性,当 时,我们得到了 的准确值,并给出了对应的极图。

关键词: 广义Turán数;匹配;偶圈;星图

Abstract

The Turán number is a classical problem in extremal graph theory. A star is a complete bipartite graph consisting of two sets of vertices: one contains a single vertex, and the other contains vertices. Let be a family of graphs. The notion denotes the maximum number of copies of in a graph on vertices that does not contain any graph from the family as a subgraph. Let and denote a matching of edges and a cycle containing edges, respectively. In this paper, by using the structural properties of stars and the convexity of combinatorial numbers, we determine for , and give corresponding extremal graphs.

Key words: Generalized Turán numbers; Matching; Even cycle; Star

参考文献 References

[1] Diestel R. Graph theory[M].北京:世界图书出版公司北京公司, 2008.

[2] Alon N, Shikhelman C. Many T copies in H-free graphs[J]. Journal of Combinatorial Theory Series B, 2016, 121: 146-172. 

[3] Chase Z. The maximum number of triangles in a graph of given maximum degree[J]. Advances in Combinatorics, 2020, 10(10): 1-5. 

[4] Ergemlidze B, Methuku A, Sali N, et al. A note on the maximum number of triangles in a -free graph[J]. Journal of Graph Theory, 2019, 90:227-230. 

[5] Gerbner D. On Turán-good graphs[J]. Discrete Mathematics, 2021, 344: 112445.

[6] Gerbner D, Győri E, Methuku A et al. Generalized Turán problems for even cycles[J]. Journal of Combinatorial Theory Series B,2020, 145: 169–213。

[7] Grzesik A. On the maximum number of five-cycles in a triangle-free graph[J]. Journal of Combinatorial Theory Series B,2012, 102: 1061–1066.

[8] Hatami H, Hladký J, Král D et al. On the number of pentagons in triangle-free graphs[J]. Journal of Combinatorial Theory Series A, 2013, 120: 722–732.

[9] Luo R. The maximum number of cliques in graphs without long cycles[J]. Journal of Combinatorial Theory Series B, 2017, 128: 219–226.

[10] Ma J, Qiu Y. Some sharp results on the generalized Turán numbers[J]. European Journal of Combinatorics, 2020, 84 : 103026.

[11] Wang J. The shifting method and generalized Turán number of matchings[J]. European Journal of Combinatorics, 2020, 85: 103057.

[12] Zhu X T, Chen Y. Generalized Turán number for linear forests[J]. Discrete Mathematics, 2022, 345: 112997.

[13] Zhu X T, Győri E, He Z et al. Stability version of Dirac’s theorem and its applications for generalized Turán problems[J]. Bulletin of the London Mathematical Society, 2023, 55: 1857–1873.

[14] Erdős P, Gallai T. On maximal paths and circuits of graphs[J]. Acta Mathematica Academiae Scientiarum Hungarica, 1959, 10: 337-356. 

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

[16] Balachandran N, Khare N. Graphs with restricted valency and matching number[J]. Discrete Mathematics, 2009, 309(12): 4176-4180. 

[17] Abbott H L, Hanson D, Sauer H. Intersection theorems for systems of sets[J]. Journal of Combinatorial Theory Series A, 1972, 12: 381–389.

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

[19] Gerbner D. On Turán problems with bounded matching number[J]. Journal of Graph Theory, 2024, 106 : 23–29.

[20] Ma J, Hou X. Generalized Turán problem with bounded matching number[J]. Archive, 2023.

[21] Zhu X T, Chen Y. Extremal problems for a matching and any other graph[J]. Journal of Graph Theory, 2025, 109: 19-24.

[22] Berge C. Sur le couplage maximum d’un graphe[J]. Comptes Rendus de l’Académie des Sciences Paris, 1958, 247: 258–259.

引用本文

任荣杰, 关于匹配和偶圈的广义 Turán问题[J]. 国际应用数学进展, 2025; 7: (2) : 1-7.