摘要
本文证明了两类特殊的循环图是(3,q)-图,从而得到:当q≥4时,r(3,q)≥5*q-13;当q≥7且为奇数时,r(3*q)≥7·q-33.
Ramsey number r(3,q) ia the least integer r such that for any graph C on r vertices, there exists either a clique of size 3 (denoted by K,) or an independent set of size q.As their simple and symmetric structures, cyclic graphs are often constructed to obtain better lower bounds of r(3,q). A graph C on n vertices is cyclic if there exists a set I = {i1 ,i1,…ik} , l≤i1<i2<…<ik≤n/2, so that the vertices of G can be identified with the integers modula n and two vertices s and t of G are joined by an edge if |s-t| ∈ I or n- |s-t| ∈ I.With the help of a microcomputer, we prove that two special kinds of cyclic graphs have neither K3 nor q-independent set, and consequently obtain two formulas about lower bounds. The following theorems and corollaries are our main results. Theorem 3.1 Let q≥4, n=5·q-14, k = [(q-1)/27, i1-1, i2=3, i1-i1-t+5 (j = 3, 4, …? k). The eyelic graph Gq with n vertices and 1={i1,i2, ≤, ik} has neither K, nos q-independent set.Corollary 3.1 r(3,q≥5·q-13 if q≥4.Theorem 3.2 Let q≥7 and q be an odd integer, n=7·q-34, k= (q-l)/2,The cyclic graph Cq with n vertices and I={i1, i29 …? ik} has neither K, norq-independent set.Corollary 3.2 r(3,q)≥7·q-33 if q≥7 and q are odd.
出处
《北京大学学报（自然科学版）》
CAS
CSCD
北大核心
1992年第3期309-315,共7页
Acta Scientiarum Naturalium Universitatis Pekinensis
基金
国家自然科学基金
关键词
RAMSEY数
下界
RAMSEY图
循环图
Ramsey numbers
Formulas of lower bounds of Ramsey numbers
Ramsey graphs
Cyclic graph
