雙星圖的Ramsey數(shù)的上界

余　培， 李雨生

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

?

雙星圖的Ramsey數(shù)的上界

余培， 李雨生

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

摘要：對給定的兩個圖G和H, Ramsey數(shù)R(G,H)是最小的正整數(shù)N，使得對完全圖KN的邊任意紅/藍(lán)著色，則或者存在紅色子圖G，或者存在藍(lán)色子圖H.雙星B(m,n)為直徑是3,有兩個中心頂點(diǎn), 其頂點(diǎn)度分別為m+1和n+1的樹.得到，當(dāng)n>m時,R(B(m,n))<2n+m+2；當(dāng)n=m或n=m+1時, R(B(m,n))=2m+n+2.

關(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ù)是組合數(shù)學(xué)中公認(rèn)的難題.以Tn表示具有n個頂點(diǎn)的樹.作為最簡單的圖類,其Ramsey數(shù)R(Tn)格外引人關(guān)注.兩種經(jīng)典的樹圖,星K1,n-1和路Pn的Ramsey數(shù)已知如下,分別見文獻(xiàn)[1-2]和文獻(xiàn)[3].

R(Pn)=n+n2—1

引理2設(shè)n為大于1的正整數(shù),則.

Erd?s和Faudree等[4]得到R(Tn)的最優(yōu)下界4n/3-1，對于上界有一個經(jīng)典的猜想.

猜想1設(shè)n是大于1的正整數(shù).是否任何樹Tn都滿足R(Tn)≤R(K1,n-1).

這個猜想沒有獲得任何證實(shí),但可以看到R(Pn)是滿足猜想1的.本文研究一類特殊的樹: 雙星圖B(m,n).它是直徑為3,有兩個中心頂點(diǎn),其頂點(diǎn)度分別為m+1和n+1的樹.直觀地講，就是用一條邊連接兩個星K1，m和K1，n的中心點(diǎn).如沒有特殊說明，文中假設(shè)n≥m.對于B(m,n),文中求出了它的Ramsey上界,同時得到它也滿足猜想1.

如果用k種顏色對圖G的頂點(diǎn)進(jìn)行著色,使得兩個相鄰的頂點(diǎn)有不同的顏色則稱圖G是可k真著色的.將真著色中的最小k稱為圖G的色數(shù),記為x(G).用s(G)表示對G進(jìn)行x(G)點(diǎn)著色時,相同顏色頂點(diǎn)類所含頂點(diǎn)數(shù)的最小值.Burr[5]得到Ramsey數(shù)的一般下界.

引理3若圖G和H滿足,G連通且G的頂點(diǎn)數(shù)大于等于s(H), 則:

對B(m,n)而言,x(B(m,n))=2,s(B(m,n))=m+1, 故可得到推論1的結(jié)果.

推論1當(dāng)正整數(shù)n≥m時,R(B(m,n))≥2m+n+2.

在有關(guān)雙星B(m,n)的Ramsey數(shù)的研究中, Guo和Volkman[6]得到R(B(1,n))的值.最近Bahlas和Spencer[7]得到下面的結(jié)果：①當(dāng)m=2,n≥3時，R(B(2,n))≤2n+3.②當(dāng)m≥3,m+2≤n≤2m-1時，R(B(m,n))≤2n+m+1.③當(dāng)m≥3,n∈{m,m+1} 時，R(B(m,n))≤2m+n+1.

本文擴(kuò)充了①～③的結(jié)果,同時指出文獻(xiàn)[7]中得到的③中的結(jié)果是有問題的，這里修正為定理1并給出相應(yīng)的證明.

定理1當(dāng)n=m或n=m+1時,R(B(m,n)) =2m+n+2.

定理2當(dāng)n≥m時，R(B(m,n))≤2n+m+1.

2證明

給定圖G, 用|G|表示圖G的頂點(diǎn)個數(shù),N(v)和d(v)分別表示頂點(diǎn)v的鄰域和度數(shù). 給圖G的邊紅/藍(lán)著色時,記Nr(v)={u∈G| {u,v}是紅邊}是v的紅鄰域，dr(v)=|Nr(v)|為其紅色度.類似地定義藍(lán)鄰域Nb(v)和藍(lán)色度db(v).

在證明定理1之前,先引入引理4并給出相應(yīng)的證明.

引理4已知正整數(shù)m,n,N滿足n≥m, 2m+n+2≤N≤2m+2n+1.給完全圖KN的邊任意紅/藍(lán)著色,若不含單色B(m,n),則對KN中任意點(diǎn)v, 均有:

證明若存在頂點(diǎn)v滿足dr(v)≥m+n+1, 則對Nr(v)中任意點(diǎn)u,均有dr(u)≤m,否則存在紅色B(m,n).由于dr(u)+db(u)=N-1,故db(u)≥N-1-m≥m+n+1. 類似的分析可知,對Nb(u)中任意w均有db(w)≤m,dr(w)≥m+n+1.若Nr(v)和Nb(u)的交集非空，取x為其中一點(diǎn)，則dr(x)≤m且dr(x)≥m+n+1，矛盾.若Nr(v)和Nb(u)的交集為空，則：N≥|Nr(v)|+|Nb(u)|+1≥2(m+n+1)+1，矛盾.故對任意點(diǎn)v均有dr(v)≤m+n,類似地db(v)≤m+n.此時若KN中存在一點(diǎn)v滿足dr(v)=m+n，則db(v)=N-1-(m+n)≥m+1. 對Nr(v)中任意點(diǎn)w,由于db(w)≤m+n，故dr(w)≥N-1-(m+n)≥m+1.若w與Nb(v) 之間存在紅邊，則存在w,v為中心點(diǎn)的紅色B(m,n),矛盾.故Nr(v)與Nb(v)之間全是藍(lán)邊，此時{v∪Nr(v)}與Nb(v)之間包含藍(lán)色完全二部圖Km+n+1,m+1, 從而有藍(lán)色B(m,n),矛盾.故對KN中任意點(diǎn)v,均有dr(v)≤m+n-1，類似的,db(v)≤m+n-1.

由dr(v)+db(v)=N-1可知N-m-n≤dr(v),db(v)≤m+n-1,證畢.

定理1的證明當(dāng)n=m或n=m+1時,由推論1可知，R(B(m,n))≥2m+n+2. 下面只需證：R(B(m,n))≤2m+n+2.

記N=2m+n+2,給完全圖KN的邊任意紅/藍(lán)著色，記R和B為所得到的紅色子圖和藍(lán)色子圖.假設(shè)不含單色B(m,n),由引理4知，對KN中任意點(diǎn)v,均滿足dr(v),db(v) 落在區(qū)間[m+2,m+n-1]內(nèi),其中m+2≥n+1.不妨設(shè)dr(v)=m+n-a，db(v)=m+1+a,其中1≤a≤n-2.考慮Nr(v)與Nb(v)之間邊的連接情況.Nr(v)中的任意點(diǎn)w到Nb(v)中至多有a條紅邊，否則將會存在一個以w,v為中心點(diǎn)的紅色B(m,n)；類似地Nb(v)中任意點(diǎn)w到Nr(v)中至多有n-a-1條藍(lán)邊，否則將存在一個以v,w為中心的藍(lán)色B(m,n).因此Nr(v)與Nb(v)之間最多有a(m+n-a)+(n-a-1)(m+1+a)條邊，但經(jīng)驗算：

這產(chǎn)生矛盾.故原假設(shè)不成立，從而存在單色B(m,n).證畢.

定理2的證明記N=2n+m+1, 給完全圖KN的邊任意紅/藍(lán)著色，記R和B為所得到的紅色子圖和藍(lán)色子圖.

情形1m+1≤n≤2m-1時,用類似于定理1的證明或直接引用文獻(xiàn)[7]中的結(jié)果，可知此時定理成立.

情形2n≥2m時，對m進(jìn)行歸納證明.當(dāng)m=1時，N=2n+2.對KN中任意點(diǎn)v,由于dr(v)+db(v)=N-1=2n+1,故可設(shè)dr(v)≥n+1.在Nr(v)在中選取集合A滿足|A|=n+1，設(shè)C=V(KN)(v∪A) 則 |C|=n.若A中存在一點(diǎn)u與C中點(diǎn)連紅邊，則存在紅色B(1,n),定理成立.否則，A和C可形成藍(lán)色完全二部圖Kn+1,n,故存在藍(lán)色B(1,n).因此當(dāng)m=1時，定理成立.

假設(shè)當(dāng)m≤k-1時，定理成立.

當(dāng)m=k時, 假設(shè)不含單色B(k,n)，由引理4知，對KN中任意點(diǎn)v，均有dr(v),db(v)落在區(qū)間[n+1,k+n-1]內(nèi).由歸納假設(shè)知，R(B(k-1,n))<2n+k+1=N.由Ramsey數(shù)的定義可知,存在一個單色B(k-1,n),不妨假設(shè)為紅色.設(shè)該B(k-1,n)

的中心點(diǎn)為u,v且dr(u)=k,dr(v)=n+1.記A=Nr(v){u},C=V(KN)V(B(k-1,n)),則|A|=|C|=n.由于不存在紅色B(k,n),故u到C之間全是藍(lán)邊.因db(u)≥n+1>|C|，故u到A之間中存在藍(lán)邊.選取A中點(diǎn)w使得{u,w}是藍(lán)邊.考慮集合{Aw}與C之間邊的連接情況.由于不存在單色B(k,n),故{Aw}中的任意點(diǎn)x到C中至多有k-1條紅邊, 否則將存在以x,v為中心點(diǎn)的紅色B(k,n)；類似的,C中任意點(diǎn)y到{Aw}中至多有k-1條藍(lán)邊,否則集合{y,Nb(y)∩(Aw)}與集合{u,w,Cy}可形成以y,u為中心點(diǎn)的藍(lán)色B(k,n).故{Aw}與C之間最多有(k-1)(n-1)+(k-1)n條邊.但當(dāng)n≥2k時

矛盾.故原假設(shè)不成立，從而存在單色B(k,n).

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

注應(yīng)用定理1于B(1,1)=P4可得R(B(1,1))=5, 該結(jié)果與由引理2得到的R(P4)=5一致.注意到定理1中的限制n=m或n=m+1是必要的.實(shí)際上,因為K1,n+1是B(m,n)的子圖,所以有R(B(m,n))≥R(K1,n+1)≥2n+1. 因此該定理中的等式不可能對(相對于m)很大的n成立.

參考文獻(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]. Proceeding of the American Mathematical Society, 1972, 32: 389.

[3]Gerencser L, Gyárfas A. On Ramsey-type problems[J]. Annals of the University of Bucharest. Mathematical Series, 1967, 10: 167.

[4]Erd?s P, Faudree R, Rousseau C,etal. Ramsey number for Brooms [J]. Congressus Numerantiu., 1982, 35: 283.

[5]Burr S. Ramsey numbers involving graphs with long suspended paths [J]. Journal of the London Mathematical Society, 1981, 24: 405.

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

[7]Bahls P, Spencer T. On the ramsey numbers of trees with small diameter [J]. Graphs and Combinatorics, 2013, 29: 39.

An Upper Bound for the Ramsey Numbers of Bistars

YU Pei, LI Yusheng

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

Abstract：For two given graphs G and H, Ramsey number R(G,H) is the smallest integer N such that any red/blue edge-coloring of KN contains a red copy of G or a blue copy of H. Let a bistar B(m,n) be a tree of diameter three with two central vertices of degree m+1 and n+1, respectively. It is shown that R(B(m,n))<2n+m+2 for n>m; and R(B(m,n))=2m+n+2 for n=m or n=m+1.

Key words：Ramsey number; tree; bistar

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

中圖分類號：O157.5

收稿日期：2015-04-24

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