双星S2,6的平面Turán型问题的一个上界
An Upper Bound for the Planar Turán Type Problem of Double Star S2,6
DOI: 10.12677/aam.2024.134136, PDF,   
作者: 胡 越, 张 旭：北方工业大学理学院，北京
关键词: 平面Turán数；双星；极值平面图；Planar Turán Numbers； Double Stars； Extremal Planar Graphs
摘要: 极值图论是图论中的重要内容，主要研究具有某些性质的图的极值问题。平面图的Turán数是指具有n个顶点的平面图G的最大边数，其中图G不包含H作为一个子图。这个问题是由Dowden在2016年提出的。最近Ghosh等人研究了若干双星图的平面Turán数，并得到很多结果。在这里，我们将给出不含双星S2,6且任意相邻两点度数之和不等于12的平面图边数的上界，即设图G是个顶点的平面图，图中不包含S2,6作为子图且任意相邻两点度数之和不等于12，那么有。
Abstract: Extremal graph theory is an important part of graph theory, which aims to study the extremal structure of graphs with certain properties. The planar Turán number, denoted by , is the maximum number of edges in graph G on n vertices, where G does not contain H as a subgraph. This problem was initiated by Dowden in 2016. Recently, Ghosh et al. discussed the planar Turán numbers of several double stars and obtained many results. In this paper, we will give the upper bound for the number of edges in the planar graph in which there does not exist a double star S2,6 and degree sum of adjacent vertices is not equal to 12. That is, if the graph G is a plane diagram of vertices, and the graph does not contain S2,6 as a subgraph, and the sum of the degrees of any adjacent two points is not equal to 12, then .
文章引用：胡越, 张旭. 双星S2,6的平面Turán型问题的一个上界[J]. 应用数学进展, 2024, 13(4): 1463-1469. https://doi.org/10.12677/aam.2024.134136

参考文献

[1] Mantel, W. (1907) Problem 28. Winkundige Opgaven, 10, 60-61.
[2] Dzido, T. (2013) A Note on Turán Numbers for Even Wheels. Graphs and Combinatorics, 29, 1305-1309. [Google Scholar] [CrossRef] 
[3] Dzido, T. and Jastrzȩbski, A. (2018) Turán Numbers for Odd Wheels. Discrete Mathematics, 341, 1150-1154. [Google Scholar] [CrossRef] 
[4] Fang, L., Zhai, M. and Wang, B. (2022) Planar Turán Number of Intersecting Triangles. arXiv: 2007.09650v1
[5] Györi, E., Paulos, A., Salia, N., et al. (2022) Generalized Planar Turán Numbers. arXiv: 2002.04579v2
[6] Füredi, Z. and Jiang, T. (2014) Hypergraph Turán Numbers of Linear Cycles. Journal of Combinatorial Theory, Series A, 123, 252-270. [Google Scholar] [CrossRef] 
[7] Gimenez, O. and Noy, M. (2009) Asymptotic Enumeration and Limit Laws of Planar Graphs. Am Math Soc, 22, 309-329. [Google Scholar] [CrossRef] 
[8] McDiarmid, C., Steger, A. and Welsh, D. (2005) Random Planar Graphs. Journal of Combinatorial Theory, Series B, 93, 187-205. [Google Scholar] [CrossRef] 
[9] Lan, Y., Shi, Y. and Song, Z.X. (2019) Extremal H-Free Planar Graphs. The Electronic Journal of Combinatorics, 26, Article Number P2.11. [Google Scholar] [CrossRef] 
[10] Lan, Y., Shi, Y. and Song, Z.X. (2024) Planar Turán Numbers of Cubic Graphs and Disjoint Union of Cycles. arXiv:2202.09216v2
[11] Ghosh, D., Györi, E., Paulos, A. and Xiao, C.Q. (2022) Planar Turán Number of Double Stars. SIAM Journal on Discrete Mathematics, 36. arXiv:2110.10515v3 [math.CO] [Google Scholar] [CrossRef] 

为你推荐