关于2-中心蜘蛛树的Erdo″s-So′s猜想

doi:10.3969/j.issn.0253-2778.2020.03.005

中国科学技术大学学报 ›› 2020, Vol. 50 ›› Issue (3): 289-293.DOI: 10.3969/j.issn.0253-2778.2020.03.005

关于2-中心蜘蛛树的Erdo″s-So′s猜想

王仕成，侯新民

中国科学技术大学数学科学学院，安徽合肥 230026

收稿日期:2019-05-22 修回日期:2019-05-28 接受日期:2019-05-28 出版日期:2020-03-31 发布日期:2019-05-28

The Erdo″s-So′s conjecture for 2-center spiders

WANG Shicheng, HOU Xinmin

Received:2019-05-22 Revised:2019-05-28 Accepted:2019-05-28 Online:2020-03-31 Published:2019-05-28
Contact: HOU Xinmin
About author:WANG Shicheng, male, Master candidate. Research field: Combinatorial graph theory. E-mail: wsc20161@mail.ustc.edu.cn

摘要/Abstract

摘要： Erdo″s-So′s 猜想：如果图G平均度大于k-2,则G包含任一k个顶点的数. 蜘蛛树是指最多只有一个点度超过2的树. 范更华、洪艳梅和刘清海证明了该猜想对所有蜘蛛树成立. 本文我们定义2中心蜘蛛树为至多两个相邻点度超过2的树并且证明了 Erdo″s-So′s 猜想对腿长至多为2的2中心蜘蛛树都成立.

关键词: Erdo″s-So′s猜想, 树, 蜘蛛树, 2-中心蜘蛛树

Abstract: The Erdo″s-So′s Conjecture states that if G is a graph with average degree more than k-2, then G contains every tree on k vertices. A spider can be seen as a tree with at most one vertex of degree more than two. Fan, Hong, and Liu proved that the conjecture holds for spiders.

Key words: Erdo″s-So′s conjecture, tree, spider, 2-center spider

中图分类号:

O157.4

王仕成，侯新民. 关于2-中心蜘蛛树的Erdo″s-So′s猜想[J]. 中国科学技术大学学报, 2020, 50(3): 289-293.

参考文献

［1］
ERDS P. Extremal Problems in Graph Theory[M]. Fiedler (Ed.), Theory of Graphs and its Applications, Academic Press, 1965: 29-36.
[2] ERDS P, Gallai T. On maximal paths and circuits of graphs[J]. Acta Math. Acad. Sc.i Hungar., 1959, 10: 337-356.
[3] FAN G. The Erds-Sós conjecture for spiders of large size[J]. Discrete mathematics, 2013, 313: 2513-2517.
[4] FAN G, HONG Y, LIU Q. The Erds-Sós conjecture for spiders[J]. Preprint, arXiv:1804.06567, 2018.
[5] FAN G, SUN L. The Erds-Sós conjecture for spiders[J]. Discrete Math., 2007, 307(23): 3055-3062.
[6] MOSER W, PACH J. Recent Developments in Combinatorial Geometry[M]// New Trends in Discrete and Computational Geometry, New York: Springer, 1993.
[7] KALAIG G. Micha perles geometric proof of the Erds-Sós conjecture for caterpillars[EB/OL]. [2018-05-22]https://gilkalai.wordpress.com/2017/08/29/micha-perles-geometric-proof-of-the-erdos-sos-conjecture-for-caterpillars/ (2017). Accessed 19 April 2018.
[8] MCLENNANA. The Erds-Sós Conjecture for trees of diameter four[J]. J. Graph Theory, 2005, 49(4): 291-301.
[9] SIDORENKO A F. Asymptotic soultion for a new class of forbidden r-graphs[J]. Combinatorica, 1989, 9: 207-215.
[10] HOU X, LV C. Bipartite version of the Erds-Sós conjecture[J]. J. Math. Research Appl., in press.
[11] WOZNIAK M. On the Erds-Sós conjecture[J]. J Graph Theory, 1996, 21: 229-234.

（上接第281页）

[15] SUN W, XIONG B S, HUANG J P, et al. Fault diagnosis of a rolling bearing using wavelet packet de-noising and LMD[J].Journal of Vibration and Shock, 2012, 31: 153-156.
[16] YAO Q B, YANG Z C, LI B. Damping identification of materials using wavelet transform[J]. Mechanical Science and Technology for Aerospace Engineering, 2007, 26: 850-855.
[17] WANG C, ZHU H P, WANG B. Identifying damping ratio of cable structures using complex wavelet transform[J]. Journal of Huazhong University of Science and Technology: Natural Science Edition, 2012, 40: 115-118.
[18] YING H Q, LIU J M, SHEN S. Half-power bandwidth method and INV damping ration solver study[J]. Noise and Vibration Control, 2006, 25: 4-6.

()
()

[1]	火清羿. 染色数为5和6的图中的圈长[J]. 中国科学技术大学学报, 2021, 51(5): 374-381.
[2]	张岩昊，时伟华. 齐次树和完全图上具有合作机制的接触过程的极限定理[J]. 中国科学技术大学学报, 2020, 50(6): 793-800.
[3]	吴加禹，李永坤，许胤龙. 一种读写均衡的高性能键值存储系统[J]. 中国科学技术大学学报, 2020, 50(6): 825-831.
[4]	冯群强，邹纯，李兴. 随机k-树的最大度数[J]. 中国科学技术大学学报, 2020, 50(3): 328-334.
[5]	黄子扬，侯新民. 树图中度数受限的大导出子图[J]. 中国科学技术大学学报, 2019, 49(8): 603-605.
[6]	冯群强，郑伯泽. 一种随机树度分布的解析方法[J]. 中国科学技术大学学报, 2019, 49(3): 173-181.
[7]	崔文泉，黄禹侨. 高维数据情形下的一种基于随机投影的集成分类方法[J]. 中国科学技术大学学报, 2019, 49(12): 974-984.
[8]	朱一波，鲍培明，吉根林. 一种用户频繁移动模式并行挖掘算法[J]. 中国科学技术大学学报, 2018, 48(1): 57-64.
[9]	周涛，陆惠玲，魏兴瑜，夏勇. 基于Piella框架和DT-CWT的肺癌PET/CT自适应融合算法[J]. 中国科学技术大学学报, 2017, 47(1): 10-17.
[10]	汪迁，李杨，都思丹. 三维显微图像中神经元树突棘自动检测与分析[J]. 中国科学技术大学学报, 2014, 44(2): 160-164.
[11]	许力，蒋佳铭. 无线多跳网络中基于声誉机制的可靠组播协议[J]. 中国科学技术大学学报, 2011, 41(10): 928-934.
[12]	张佳志，黄游，刘伟，梁好均. 大孔吸附树脂对芳香族化合物的吸附研究[J]. 中国科学技术大学学报, 2010, 40(7): 706-711.
[13]	张旭东，邵晓丽，张远旭，张华堂，何有文. 树鼩PD-1基因的分离、鉴定及表达分析[J]. 中国科学技术大学学报, 2009, 39(7): 714-721.
[14]	邵晓丽，张旭东，张远旭，张华堂，何有文 . 树鼩IL-2Rα（CD25）基因的分离、鉴定及表达分析[J]. 中国科学技术大学学报, 2009, 39(7): 722-727.

关于2-中心蜘蛛树的Erdo″s-So′s猜想

The Erdo″s-So′s conjecture for 2-center spiders

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价