关于两个中心四腿蜘蛛的Erdös-Sós猜想
On the Erdös-Sós Conjecture for 2-Center 4-Leg Spiders
DOI: 10.12677/pm.2025.1512291, PDF,    国家自然科学基金支持
作者: 张 扬, 周垂香：福州大学数学与统计学院，福建 福州
关键词: Erdös-Sós猜想；树；蜘蛛树；圈；路；Erdös-Sós Conjecture； Tree； Spider； Cycle； Path
摘要: Erdös-Sós猜想是极值图论的一个经典问题，围绕此猜想有许多相关结论。猜想的内容是：如果一个图G有n个点且 e( G )> ( k−1 )n 2 ，则G包含任何k条边的树。蜘蛛是指最多有一个点度数超过2的树，2-中心蜘蛛是指只有两个点的度数超过2的树。Erdös-Sós猜想已经被证明对于3条腿的蜘蛛成立，在此方法上，本文利用图的结构进行分类讨论并证明了猜想对于每一中心有一条2长腿的2-中心4腿蜘蛛成立。
Abstract: The Erdös-Sós conjecture is a classic problem in extremal graph theory, with many related conclusions surrounding it. The Erdös-Sós conjecture states that every graph with n vertices and e( G )> ( k−1 )n 2 contains every tree with k edges. A spider is defined as a tree with at most one vertex of degree greater than 2. A 2-center spider is a tree which has only two vertices degrees greater than 2. The Erdös-Sós conjecture has been proven for spiders with 3 legs. Basing on the method of constructing, we prove that the conjecture is true for spiders of 2-center spider with 4 legs and each center has a leg of length 2.
文章引用：张扬, 周垂香. 关于两个中心四腿蜘蛛的Erdös-Sós猜想[J]. 理论数学, 2025, 15(12): 34-40. https://doi.org/10.12677/pm.2025.1512291

参考文献

[1] Erdös, P. (1965) Extremal Problem in Graph Theory. In: Fiedler, Ed., Theory of Graphs and Its Applications, Academic Press, 29-36.
[2] Brandt, S. and Dobson, E. (1996) The Erdős-Sós Conjecture for Graphs of Girth 5. Discrete Mathematics, 150, 411-414. [Google Scholar] [CrossRef] 
[3] Eaton, N. and Tiner, G. (2013) On the Erdős-Sós Conjecture for Graphs Having No Path with k + 4 Vertices. Discrete Mathematics, 313, 1621-1629. [Google Scholar] [CrossRef] 
[4] Yin, J. and Li, J. (2004) The Erdős-Sós Conjecture for Graphs Whose Complements Contain No C 4. Acta Mathematicae Applicatae Sinica, English Series, 20, 397-400. [Google Scholar] [CrossRef] 
[5] Erdős, P. and Gallai, T. (1959) On Maximal Paths and Circuits of Graphs. Acta Mathematica Academiae Scientiarum Hungaricae, 10, 337-356. [Google Scholar] [CrossRef] 
[6] McLennan, A. (2005) The Erdös-Sós Conjecture for Trees of Diameter Four. Journal of Graph Theory, 49, 291-301. [Google Scholar] [CrossRef] 
[7] Fan, G., Hong, Y. and Liu, Q. (2018) The Erdös-Sós Conjecture for Spiders.
[8] Fan, G. and Sun, L. (2007) The Erdös-Sós Conjecture for Spiders. Discrete Mathematics, 307, 3055-3062. [Google Scholar] [CrossRef] 
[9] Fan, G. and Huo, Z. (2016) The Erdös-Sós Conjecture for Spiders of Four Legs. Journal of Combinatorics, 7, 271-283. [Google Scholar] [CrossRef] 
[10] 王仕成, 侯新民. 关于2-中心蜘蛛树的Erdös-Sós猜想[J]. 中国科学技术大学学报, 2020, 50(3): 289-293.

为你推荐