扇形图与匹配图的临界星图Ramsey数

对于完全图Kn和一个额外的顶点v,通过在v与Kn之间添加k条边所得出的图,记为KnK1,k.设G和H是任意的图,临界星图Ramsey数r*(G,H)定义为最小的正整数k,使得图KN-1K1,k的任意红蓝2-边着色,或者存在单色的红色子图G,或者存在单色的蓝色子图H,这里N指的是Ramsey数r(G,H).文中找到了r(Fn,mK2)的所有临界图,利用这些临界图得到了临界星图Ramsey数r*(Fn,mK2)=m+1,nm≥1,以及r*(Fn,mK2)=2 m,n≤m,这里Fn=K1+nK2是扇形图.     

具有固定匹配数的极值k-部k-一致超图的结构

设V1,V2,…,Vk为k个有限集,i∈{1,2,…,k},ni△=|Vi|,n△=min{n1,n2,…,nk}.H为一个以V1,V2,…,Vk为顶点类的k-部k-一致超图,v(H)表示H的匹配数,|H|表示H的边数.设t为一个给定的整数.首先证明:如果v(H)≤t,则|H|≤tn1n2…nk/n.当v(H)=t,|H|=tn1n2…nk/n时,确定了H的结构.     

Sm∨Fn的全色数

设G(V,E)是阶数至少是2的简单连通图,k是正整数,若f是从V(G)∪E(G)到{1,2,…,k}的一个映射,使得:对于任意的uv,vw∈E(G),u≠w,有f(uv)≠f(vw);且对于任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的一个k-全染色(简记成k-TC of G).而χt(G)=min{k|k-TC of G},称为G的全色数.设G和H是点边都不相交的简单图,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)},则称G∨H是G与H的联图.给出m 1阶星和n 1阶扇的联图的全色数.     

二分图中含有经过给定点的大圈的2-因子的度条件

设G=(V1,V2;E)是一个二分图, 其顶点数目满足V1=V2=n≥sk,s和k是满足s≥3并且k≥2的两个正整数. 如果σ1,1≥2「(1-1/s)n」+k, 那么G对的任意k个顶点v1,v2,…,vk,G有一个包含k个点不交圈G1,G2,…的因子,使得vi∈V(ci)且Ci≥2s.     

图的独立数与分数一致性

设G是一个顶点集为V(G),最小度为δ(G),独立数为α(G)的图,k≥2是整数。图G的支撑子图F称作是图G的分数k-因子,如果对于每一个x∈V(F)都有dh G(x)=k。如果对于图G的每条边e,图G都有一个分数k-因子包含它而且同时有一个分数k-因子不包含它,则称图G为分数k一致图。证明了如果δ(G)≥k+2,且α(G)≤4k(δ-k-1)/(k+1)2,则图G是一个分数k一致图。     

长圈的邻域并条件的推广

本文证明了若G为一个k(k≥2)连通简单图,最小度为,δV(G)=n≥3,X 1,X 2,……,X k是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2……k)中任意两个不相邻点u,v,都有N(u)∪N(v)≥n-δ,则X在G中可圈。并给出几个相关推论.     

1-坚韧图中具有邻域并型的X-最长圈

设G是连通图,XV(G), G[X]是G的X生成子图.记α(X)=max{|S|:S是G[X]的顶点独立集}, ak(X)=MIN{k∑i=1d(vi):{v1,v2,...,vk}是G[X]的顶点独立集}, NCk(x)=min{|kUi=1N(vi)|:{v1,v2,...,vk}是G[X]的顶点独立集}(k≥2). 本文得到如下结果:对于n阶的1-坚韧图(n≥3), XV(G)且σ3(X)≥n+r≥n, r为正整数,则存在一个圈C满足|C(X)|≥min{|X|,|X|+NCr+5+ε(n+r)(X)-α(X)}, 其中ε(i)=3「1/3i」.-1/3i 此结果推广了H.J.Broersma等在文献[2]中的结果.     

关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。     

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

完全三部图色唯一性数值条件的改进

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G■H),则称图G是色唯一图.这里通过比较图的三角形子图和无弦四边形子图的个数,讨论了完全三部图K(n-k,n-v,n)的色唯一性.证明了若n≥v~2(k-v/3)/4+v,k≥v≥2,则完全三部图K(n-k,n-v,n)是色唯一图;若n≥k+2,k≥2,则完全三部图K(n-k,n-2,n)是色唯一图.