馬珩博，尹建華

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

關(guān)于蘊(yùn)含Ramsey數(shù)rpot(Kn-ke,Kt-qe)問題

馬珩博，尹建華

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?570228)

蘊(yùn)含Ramsey數(shù)； 可圖序列； 實(shí)現(xiàn)

1 引言

定理1[3]若G是一個(gè)n階無孤立點(diǎn)的圖G滿足α(1)(1)≤n-1，且t≥2，則

rpot(G,Kt)≥max{2t+n-α(1)(G)-2,n+t-2} .

定理2[3]對(duì)于n≥t≥3，rpot(Kn，Kt)=2n+t-4，除了當(dāng)n=t=3時(shí)，rpot(K3，K3)=6.

根據(jù)定理2，容易得到以下結(jié)論：若A和B分別是4階以上的完全圖C和D的子圖，則

rpot(A,B)≤rpot(C,D)=max{|C|,|D|}+|C|+|D|-4.

一個(gè)圖G的2-獨(dú)立數(shù)，記為α(2)(G)，是G的一個(gè)導(dǎo)出子圖H的最大階數(shù)且滿足H的最大度Δ(H)≤2 .

rpot(G,Kt-ke)≥2t+n-α(2)(G)-k-1.

根據(jù)定理3，容易得到關(guān)于rpot(Kn-ke,Kt-qe)的下界推論.

推論1 當(dāng)n,t≥5時(shí)，

rpot(Kn-ke,Kt-qe)≥max{2t+n-x(k)-q,2n+t-x(q)-k},

其中,當(dāng)s=0或1時(shí)x(s)=4，當(dāng)s≥2時(shí)x(s)=5.

根據(jù)定理2和推論1，有以下

推論2 若n≥t≥4，則rpot(Kn，Kt-e)=2n+t-4.

推論3 若n≥t≥4，則2n+t-5≤rpot(Kn-e,Kt-e)≤2n+t-4.

2 定理3的證明

引理1得證.

引理2得證.

推理4得證

推論5得證.

引理3得證.

推論6得證.

引理4得證.

定理3的證明 考慮可圖序列π=((2t+n-α(2)(G)-k-3)n-a(2)(G)-1，(n-α(2)(G)+1)2t-k-1).易見，π的實(shí)現(xiàn)為Kn-α(2)(G)-1∨S，其中∨表示聯(lián)圖，S為一個(gè)2t-k-1階正則圖.假設(shè)Kn-α(2)(G)-1∨S包含G作為子圖,則G中有至少α(2)(G)+1個(gè)頂點(diǎn)落在S中,從而G的2-獨(dú)立數(shù)至少為α(2)(G)+1，不可能.故π不是蘊(yùn)含G可圖的.

綜上所述，rpot(G,Kt-ke)>2t+n-α(2)(G)-k-2.由于rpot(G,Kt-ke)是一個(gè)正整數(shù)，所以rpot(G,Kt-ke)≥2t+n-α(2)(G)-k-1.

定理3的得證.

[1] Yin J H,Li J S. Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size[J]. Discrete Mathematics，2005(301):218-227.

[2] Yin J H.A characterization for a graphic sequence to be potentially Gr-graphic[J].Science China Mathematics,2010(11):2 893-2 905.

[3] Busch A ，F(xiàn)errara M ，Hartke S G， et al. A degree sequence variant of graph Ramsey number[J]. Graphs and Combinatorics，2014(30):847-859.

Problem of Potentially Ramsey Number rpot(Kn-ke,Kt-qe)

Ma Hengbo, Yin Jianhua

(College of Information Science and Technology, Hainan University, Haikou 570228, China)

potentially Ramsey Number; graphic sequences; realization

2016-07-01

海南省自然科學(xué)基金(2016CXTD004)

馬珩博(1993-)，男，山西大同人，海南大學(xué)2015級(jí)碩士研究生，研究方向：蘊(yùn)含Ramsey數(shù)，E-mail：1693951315@qq.com

尹建華(1970-)，男，湖南祁陽人，教授，博士，研究方向：圖論及其應(yīng)用，E-mail: yinjh@hainu.edu.cn

1004-1729(2016)04-0319-05

O 157.5

A DOl：10.15886/j.cnki.hdxbzkb.2016.0048