Ramsey numbers of long cycles versus books or wheels
Ramsey numbers of long cycles versus books or wheels
复制标题
拉姆齐长周期数与书籍或轮子的比较
DOI：
10.1016/j.ejc.2009.07.004
复制
发表时间：
2010-04
影响因子：
1
通讯作者：
Shi, Lingsheng
中科院分区：
文献类型：
--
作者：
Shi, Lingsheng
给定两个图G1和G2，用G1 <$G2表示由G1 <$G2通过将G1的所有顶点连接到G2的顶点而得到的图。Ramsey数R（G1，G2）是使每个n阶图G包含G1的一个拷贝或其补图G c包含G2的一个拷贝的最小正整数n。证明了一本书Bm=K2 <$Kmc对一个n阶圈Cn的Ramsey数满足R（Bm，Cn）=2n−1（n>（6 m +7）/4），改进了Faudree等人的结果，并且当m为偶数且n≥ 3 m/2 + 1或n>max{m+1，70}或n≥max{m，83}时，循环Cn对车轮Wm=K1 <$Cm的Ramsey数满足R（Cn，Wm）=2n − 1和R（Cn，Wm）= 3 n −2，这改进了Surahmat等人的结果.也证实了他们对大n的猜想。作为推论，还得到了其它稀疏图的Ramsey数.
Given two graphs G1and G2, denote by G1∗G2the graph obtained from G1∪G2by joining all the vertices of G1to the vertices of G2. The Ramsey number R(G1,G2) is the smallest positive integer n such that every graph G of order n contains a copy of G1or its complement Gccontains a copy of G2. It is shown that the Ramsey number of a book Bm=K2∗Kmcversus a cycle Cnof order n satisfies R(Bm,Cn)=2n−1 for n>(6m+7)/4 which improves a result of Faudree et al., and the Ramsey number of a cycle Cnversus a wheel Wm=K1∗Cmsatisfies R(Cn,Wm)=2n−1 for even m and n≥3m/2+1 and R(Cn,Wm)=3n−2 for odd m>1 andn≥3m/2+1 or n>max{m+1,70} or n≥max{m,83} which improves a result of Surahmat et al. and also confirms their conjecture for large n. As consequences, Ramsey numbers of other sparse graphs are also obtained.
登录
查看更多内容
影响因子：
--
作者：
null Surahmat;E. Baskoro;H. Broersma
通讯作者：
null Surahmat;E. Baskoro;H. Broersma
DOI：
10.1112/jlms/s2-18.3.392
发表时间：
1978-12
影响因子：
1.2
作者：
C. Rousseau;J. Sheehan
通讯作者：
C. Rousseau;J. Sheehan
影响因子：
0.6
作者：
V. Chvátal;F. Harary
通讯作者：
V. Chvátal;F. Harary
DOI：
10.1002/jgt.3190020110
发表时间：
1978-03
期刊：
J. Graph Theory
影响因子：
--
作者：
C. Rousseau;John T. Sheehan
通讯作者：
C. Rousseau;John T. Sheehan
DOI：
10.1016/0012-365x(74)90151-4
发表时间：
1974
期刊：
Discret. Math.
影响因子：
--
作者：
R. Faudree;R. Schelp
通讯作者：
R. Faudree;R. Schelp