一些掃帚圖的Ramsey數(shù)

余　培， 陳　明， 李雨生

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

?

一些掃帚圖的Ramsey數(shù)

余培， 陳明， 李雨生

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

摘要：給定圖G，Ramsey數(shù)R(G)是最小的正整數(shù)N，滿足對完全圖 KN的邊任意紅藍(lán)著色，則或者存在紅色子圖G或者存在藍(lán)色子圖G.掃帚圖Bk，m是將星圖K1,k的中心點(diǎn)與路Pm的一個端點(diǎn)黏成一個點(diǎn)得到的樹圖.由此得到,當(dāng)k為大于1的正整數(shù)時，R(Bk,2k-1)=4k-2且R(Bk,4)=2k+3.

關(guān)鍵詞：Ramsey數(shù)； 樹； 掃帚圖

1研究背景

本文研究的圖均為簡單圖.任給圖G和H，Ramsey數(shù)R(G,H)是最小的正整數(shù)N，滿足對完全圖KN的邊任意紅藍(lán)著色，則或者存在紅色子圖G或者存在藍(lán)色子圖H.當(dāng)G=H時，簡記R(G,G)為R(G).

Ramsey數(shù)一直都是國際上比較熱門的研究課題之一.以Tn表示具有n個點(diǎn)的樹.作為最簡單的圖類，R(Tn)的研究備受關(guān)注.其中兩類經(jīng)典的圖類是星圖和路. 記K1,n-1是星圖，也即一個點(diǎn)下面掛了n-1條邊；Pn是有n個點(diǎn)的路.它們的Ramsey數(shù)如下,分別見文獻(xiàn)[1-3].

-1.

本文的研究對象是掃帚圖Bk,m.掃帚圖Bk，m是將星圖K1,k的中心點(diǎn)與路Pm的一個端點(diǎn)黏成一個點(diǎn)后所得到的樹圖.由定義可知：B1,m是路Pm+1；Bk,1=K1,k,Bk,2=K1,k+1是星圖.Erd?s,Faudree等人在文獻(xiàn)[4]中得到：R(Tn)的最小下界能在某些Bk,m中達(dá)到，同時猜測R(Tn)的最大上界也能在某些Bk,m中達(dá)到，故研究R(Bk,m)是非常有意義的.

目前掃帚圖研究的主要結(jié)果是Erd?s,Faudree等人在文獻(xiàn)[4]中得到的，如下：

(2) 當(dāng)5≤m≤2k-1時，R(Bk,m)≤2k+m.

當(dāng)m=1,2時，Bk,1，Bk,2是星圖，由引理2可得到R(Bk,1),R(Bk,2)的值；當(dāng)m=3時，Bk,3是雙星圖，Guo和Volkman在文獻(xiàn)[5]得到R(Bk,3)的值.因此還未確定的是當(dāng)m=4，以及當(dāng)5≤m≤2k-1時的情況.本文得到如下結(jié)果.

定理1設(shè)k是正整數(shù)，則R(Bk,2k-1)=4k-2.

定理2設(shè)k≥2為正整數(shù)，則R(Bk,4)=2k+3.

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

已知圖G，以V(G)表示圖G的頂點(diǎn)集.當(dāng)給圖G的邊紅藍(lán)染色后，記其中紅色子圖為R，藍(lán)色子圖為B.已知v是圖G中的任意點(diǎn)，記N(v)={u|點(diǎn)u，v之間連邊}為點(diǎn)v的鄰域；NR(v)={u|邊[uv]是紅色}為點(diǎn)v的紅鄰域；NB(v)={u|邊[uv]是藍(lán)色}為點(diǎn)v的藍(lán)鄰域. 二部圖G(A,D)：可將圖G的頂點(diǎn)集分成兩類A和D，邊只在A和D之間存在，而A和D內(nèi)部并沒有邊的圖類.其他有關(guān)圖的定義，可參考文獻(xiàn)[6].

引理3(Jackson)已知G(A,D)是二部圖，其中k≤|D|≤2k-2.若A中任意點(diǎn)x均滿足|N(x)|≥k，則G(A,D)包含任意圈C2t，其中1≤t≤min{|A|,k}.

引理4已知樹Tn的兩個部集大小分別為a,b,則

R(Tn)≥max{2a+b-1,2b-1}

證明不妨假設(shè)b≥a.給完全圖K2a+b-2紅藍(lán)邊染色，其中紅色子圖為Ka-1∪Ka+b-1,相對應(yīng)的藍(lán)色子圖為二部圖G(a-1，a+b-1)，由于其中一個單色部集最大為a-1達(dá)不到a，故不含單色Tn.

給完全圖K2b-2紅藍(lán)邊染色，其中紅色子圖為Kb-1∪Kb-1,相對應(yīng)的藍(lán)色子圖為二部圖G(b-1,b-1),由于單色部集最大為b-1，達(dá)不到b,故不含單色Tn.

綜上有R(Tn)≥max{2a+b-1,2b-1}，證畢.

推論1已知k,m為正整數(shù)，則

R(Bk,m)≥max{k+3m/2-1,2k+2m/2-1}

定理1的證明當(dāng)k=1時，B1,1=P2，由Ramsey數(shù)的定義知R(P2)=2.

當(dāng)k=2時，Bk,2k-1=B2,3，由推論1知R(B2,3)≥6，下面來證R(B2,3)≤6.

給完全圖K6任意紅藍(lán)邊染色，則必存在一點(diǎn)的單色度大于等于3，不妨設(shè)點(diǎn)v的藍(lán)色鄰域大于等于3. 在NB(v)中取集合A0滿足|A0|=3，記C=V(K6)(A0∪v),則|C|=2.若A0與C之間存在藍(lán)邊，則存在藍(lán)色B2,3；若A0與C之間沒有藍(lán)邊，即全是紅邊，此時A0與C之間存在紅色B2,3，故R(B2,3)=6.

當(dāng)k≥3時，由推論1知R(Bk,2k-1)≥4k-2，下面只需證R(Bk,2k-1)≤4k-2.

給完全圖K4k-2任意紅藍(lán)邊染色，記染色后的圖為G.根據(jù)Ramsey數(shù)的定義，只需證明G中含有單色Bk,2k-1.由文獻(xiàn)[7]知：當(dāng)k≥3時，R(C2k)=3k-1. 因4k-2≥3k-1，所以G中含有單色C2k,不妨設(shè)其為藍(lán)色.

記D=V(G)V(C2k),則|D|=2k-2. 若C2k中存在一點(diǎn)x滿足：|NB(x)∩D|≥k-1,則G中存在藍(lán)色Bk,2k-1. 假設(shè)對C2k中任意點(diǎn)x，均有|NB(x)∩D|≤k-2.由|NB(x)∩D|+|NR(x)∩D|=|D|=2k-2知，|NR(x)∩D|≥k，故V(C2k)和D之間至少有2k2條紅色邊.從而D中存在一點(diǎn)u滿足|NR(u)∩V(C2k)|≥2k2/|D|≥k+1.在NR(u)∩V(C2k)中選取k+1個點(diǎn){u0,u1,…,uk},記集合A=V(C2k){u1,u2,…,uk},則|A|=k.

考慮紅色二部圖G(A,D)∩R. 該紅色二部圖滿足引理3的條件，故A和D之間存在紅色圈C2k.記該紅圈的頂點(diǎn)集為E.由于該紅色圈包含A，從而包含點(diǎn)u0.此時{u1,u2,…,uk}，u，u0，E可生成紅色Bk,2k-1.證畢.

當(dāng)k=1時，B1,4=P5，由引理1知，R(P5)=6；當(dāng)k≥2時，Bk，m開始存在星結(jié)構(gòu)，下面考慮此時R(Bk,4)的值.

定理2的證明由推論1知,R(Bk,4)≥2k+3，下面只需證R(Bk,4)≤2k+3.

給完全圖K2k+3任意紅藍(lán)邊染色，設(shè)G是染色后的圖.由Ramsey數(shù)的定義，只需證G含有紅色或者藍(lán)色子圖Bk,4.下面用反證法來證明，即假設(shè)G中不含有單色Bk,4,最終來推出矛盾.

(1) 當(dāng)k=2時，2k+3=7.由引理1知R(P5)=6≤7，故G中含有單色路P5，不妨設(shè)為紅色.按順序標(biāo)記該路的點(diǎn)為{x1,x2,x3,x4,x5},記路之外的兩點(diǎn)為{y1,y2}. 由于不含紅色B2,4，故集合{x2,x4}與{y1,y2}之間的邊全是藍(lán)色的.

情形1集合{x1,x5}與{y1,y2}之間存在紅色邊.

不妨假設(shè)邊[x5,y2]是紅色的.由于不含紅色B2,4，故邊[x5,y1]，[x3,y1]均是藍(lán)色的.此時{x2,x3}，y2，x4，y1，x5可生成藍(lán)色B2,4，矛盾.

情形2集合{x1,x5}與{y1,y2}之間全是藍(lán)色邊.

此時易知{x1,x2}，y2，x4，y1，x5可生成藍(lán)色B2,4，矛盾.

故當(dāng)k=2時，定理成立.

(2) 當(dāng)k≥3時，由引理2知R(K1,k+1)≤2k+3, 故G中含有單色K1,k+1,不妨設(shè)為藍(lán)色.設(shè)x為該藍(lán)色K1,k+1的中心點(diǎn)，記A=V(K1,k+1)x，D=V(G)V(K1,k+1)，則|A|=|D|=k+1.

斷言D是紅色完全圖Kk+1,即D內(nèi)的邊都是紅色的.

斷言的證明用反證法，假設(shè)D內(nèi)存在藍(lán)色邊[u,v]. 由于G不含藍(lán)色Bk,4,從而{u,v}和A之間全是紅邊.若{u,v}和D{u,v}之間存在紅色邊，則A，{u,v}和該紅邊可生成紅色Bk,4，故{u，v}和D{u,v}之間全是藍(lán)色邊.此時選取這些藍(lán)邊，按剛剛的分析可知，D內(nèi)邊全是藍(lán)色的且A與D之間的邊均為紅色.

此時在D中取一點(diǎn)w.若邊[x,w]染藍(lán)色，則A，x，w和Dw中任意兩點(diǎn)可生成藍(lán)色Bk，4,注意到此時Dw中可取兩點(diǎn)，因|D|=k+1≥3；若邊[x,w]染紅色，此時在Dw中取一點(diǎn)d1，在A中取一點(diǎn)a1，則Aa1，d1，a1，w，x可生成紅色Bk,4.無論哪種情形，所得結(jié)果均與假設(shè)矛盾，故D內(nèi)邊全是紅色的，進(jìn)而斷言成立.

下面考慮x與D之間邊的染色情況.

情形3x與D之間存在紅邊.

情形4x與D之間的邊全是藍(lán)色的.

此時在A∪D中任取集合F滿足|F|=k+1，記M=V(G){F∪x},則|M|=k+1.由斷言的分析知：M為紅色完全圖Kk+1.由F的任意性，可知A∪D是紅色完全圖K2k+2.由于2k+2≥k+4,故A∪D中含有紅色Bk,4，矛盾.故當(dāng)k≥3時，定理成立.

綜上所述，定理成立.證畢.

參考文獻(xiàn):

[1]Burr S, Roberts J. On the Ramsey numbers for stars[J]. Utilitas Mathematica, 1973, 4: 217.

[2]Chvátal V, Harary F. Generalized Ramsey theory for graphs II, small diagonal numbers[J]. Proceedings of American Mathematical Society, 1972, 32(2): 389.

[3]Gerencser L, Gyárfas A. On Ramsey-type problems[J]. Annales Universitatis Scientiarum Budapestinensis de Rolando Eotvos Nominatae Sectio Mathematica, 1967, 10: 167.

[4]Erd?s P, Faudree R, Rousseau C,etal. Ramsey numbers for brooms[J]. Congressus Numerantium, 1982, 35:283.

[5]Guo Y, Volkmann L. Tree-Ramsey numbers[J]. The Australasian Journal of Combinatorics, 1995, 11: 169.

[6]Bollobás B. Modern graph theory[M]. New York: Spring-Verlag, 1998.

[7]Faudree R, Schelp R. All Ramsey numbers for cycles in graphs[J]. Discrete Mathematics, 1974, 8(4): 313.

Ramsey Number for Some Brooms

YU Pei， CHEN Ming， LI Yusheng

(Department of Mathematics, Tongji University, Shanghai 200092, China)

Abstract：For a given graph G, Ramsey number R(G) is the smallest integer N such that any red/blue edge-coloring of KN contains a red copy or a blue copy of G. Let broom Bk,mbe a tree obtained by identifying the central vertex of a star K1,kwith an end-vertex of Pm. It is proven that R(Bk,2k-1)=4k-2 and R(Bk,4)=2k+3 for integer k>1.

Key words：Ramsey number; tree; broom

收稿日期：2015-09-07

通訊作者：陳明(1981—)，男，博士生，講師，主要研究方向為組合數(shù)學(xué)與圖論. E-mail: chen2001ming@163.com

中圖分類號：O157.5

文獻(xiàn)標(biāo)志碼：A

第一作者： 余培(1993—),男,博士生,主要研究方向為組合數(shù)學(xué)與圖論. E-mail: yupeizjy@163.com