臨界完全圖Ramsey數(shù)

李 燕， 李雨生

(同濟(jì)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 上海 200092)

1 研究背景

文中研究的圖均為簡(jiǎn)單圖.設(shè)G和H是任意的兩個(gè)圖.Ramsey數(shù)r(G,H)定義為最小的正整數(shù)r，使得圖Kr的任意紅藍(lán)二邊著色或存在單色的紅色子圖G，或存在單色的藍(lán)色子圖H.實(shí)際上，在Ramsey數(shù)的研究中，并不需要完全圖的所有邊即可找到單色的紅色子圖G或單色的藍(lán)色子圖H.因此，Hook等[1]首先在文獻(xiàn)[1]中提出臨界星圖Ramsey數(shù)r*(G,H)并確定了一些臨界星圖Ramsey數(shù).下面給出臨界星圖Ramsey數(shù)的定義.

定義1設(shè)r=r(G,H)為Ramsey數(shù)，臨界星圖Ramsey數(shù)r*(G,H)定義為最小的正整數(shù)n，使得圖Kr-K1,r-1-n的任意紅藍(lán)二邊著色或存在單色的紅色子圖G，或存在單色的藍(lán)色子圖H.

臨界星圖Ramsey數(shù)是在完全圖中刪掉最大星圖的導(dǎo)出子圖中尋找單色紅色子圖G或單色藍(lán)色子圖H.進(jìn)一步發(fā)現(xiàn)，在尋找Ramsey數(shù)的過(guò)程中，完全圖Kr的邊可以在刪掉星圖后繼續(xù)減少，仍然可能存在單色紅色子圖G或單色藍(lán)色子圖H.

定義2設(shè)r=r(G,H)為Ramsey數(shù)，臨界完全圖Ramsey數(shù)為最大的正整數(shù)n，使得圖Kr-Kn的任意紅藍(lán)二邊著色或存在單色的紅色子圖G或存在單色的藍(lán)色子圖H.

2 主要結(jié)果的證明

引理1[5]當(dāng)整數(shù)n≥5，r(W1,n,K3)=2n+1.

引理2[6]當(dāng)整數(shù)n≥4，r(Cn,K3)=2n-1.

引理3[2]當(dāng)整數(shù)n≥3，r*(Cn,K3)=n+1.當(dāng)整數(shù)n≥5，r*(W1,n,K3)=n+3.