论文部分内容阅读
Ramsey理论研究的是在一个充分大的系统中某些事先给定的子系统的存在性。Ramsey数是Ramsey理论中的一个重要分支，它研究的是系统规模的一种临界状态，即一个大的系统究竟要大到什么程度才会包含某个给定的子系统。对于给定的两个图G1和G2，图Ramsey数R(G1，G2)就是最小的正整数n，使得任一n阶图，要么G含有G1，要么图G的补图-G含有G2。一般说来，要求出图Ramsey数的准确值是非常困难的。
对于树—轮型Ramsey数R(Tn，Wm)，E．T．Baskoro等人在“On Ramsey numbers for trees versus wheels of five or six vertices”[Graphs Combinatorics 18(2002)，717-721]一文中猜测：当n≥m-1，m为偶数且Tn不是星图时，R(Tn，Wm)=2n-1；当n≥m-1，m为奇数且Tn不是星图时，R(Tn，Wm)=3n-2。该猜想已被证明当Tn是路时成立，当m为偶数时是不对的。由于当m为偶数时，2n-1是R(Tn，Wm)的一个自然的下界，人们希望知道在此种情形下，什么样的Tn满足R(Tn，Wm)=2n-1。
当m为偶数时，由于R(Tn，Wm)的值随着△(Tn)的增大可能会增大，因此若Tn满足R(Tn，Wm)=2n-1，△(Tn)应当比较小。在本篇论文中，我们主要考虑△(Tn)=3且m为偶数时R(Tn，Wm)的值，证明了当n≥9时，R(Pn(k)，W8)=2n-1，其中Pn(k)表示所有最长路阶数为n-1的n阶树，确定了R(T8，W8)的所有准确值，这些值大部分与猜想的值不一致。全文共分三章：第一章介绍了一些图论的基本概念以及Ramsey理论的历史，一些重要方法和定理。第二章主要介绍已有的有关树和轮的Ramsey数以及这方面的最新进展。第三章中我们给出了R(T8，W8)和R(Pn(k)，W8)的值及相关证明。