关于匹配和偶圈的广义 Turán问题-国际应用数学进展-CSCIED科技核心评价数据库-手机版

关于匹配和偶圈的广义 Turán问题

Generalized Turán problems for a matching and an even cycle

ES评分 0 浏览量：175 下载量：0

DOI	10.12208/j.aam.20250010
刊名	国际应用数学进展 Advances in International Applied Mathematics
年，卷(期)	2025, 7(2)
作者	任荣杰*,
作者单位	南京航空航天大学数学学院江苏南京
摘要	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.
关键词	广义Turán数；匹配；偶圈；星图
KeyWord	Generalized Turán numbers; Matching; Even cycle; Star
基金项目
页码	1-7

参考文献
相关文献

[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.

文献评论

相关学者

相关机构