A variation of a conjecture due to Erdös and Sós |
| |
基金项目: | Supported by National Natural Science Foundation of China (Nos. 10861006, 10401010)
Acknowledgements The authors are very grateful to the referees for their valuable suggestions and comments. |
| |
摘 要: | Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e(G) 〉 1/2(k - 1)n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 + 37/2+ 14 and every graph G on n vertices with e(G) 〉 1/2 (k- 1)n, we prove that there exists a graph G' on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.
|
关 键 词: | Erdoes 国有企业 猜想 变异 电子商务 顶点 度序列 猜测 |
本文献已被 维普 SpringerLink 等数据库收录! |