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

设P(G,λ)是图G的色多项式.如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.通过比较图的特征子图的个数,讨论了由文献[Koh K M,Teo K L.The search for chromatically unique graphs.Graphs and Combinatorics,1999,6:259-285]中提出的猜想(若n≥k+2,则完全三部图K(n-k,n,n)是色唯一图);推广了文献[Liu Ru-yin,Zhao Hai-xing,Ye Cheng-fu.A complete solution to a conjecture on chromatic unique of complete tripartite graphs.Discrete Mathematics,2004,289:175-179]中的结果(若n≥k+2≥4,则K(n-k,n,n)是色唯一图;若n≥2k≥4,则K(n-k,n-1,n)是色唯一图);证明了若n≥k+2≥4,则K(n-k,n,…,n)是色唯一图,若n≥k+2≥4,则K(n-k,n-1,n,…,n)是色唯一图.

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

设P(G,λ)是图的色多项式。如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称图G是色唯一图.这里通过比较t+1色类的色划分数目,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,当min(n1,n2,…,nt)充分大时,完全t部图K(n1,n2,…,nt)是否是色唯一图?)。改进了文献[5]中的结果。证明了若Σ1≤i≤ta2i=T,min{n+a1,n+a2,…,nt+at,n-1}≥(T+1)/2,则K(n+a1,n+a2,…,n+at)是色唯一图(其中ai是实数,n+ai是正整数)。从而证明了若|ni-nj|≤k(i,j=1,2,…,t),min{n1,n2,…,nt}≥tk2/8+1,则K(n1,n2,…,nt)是色唯一图。

关于完全t部图K(n_1,n_2,…,n_t)的色唯一性

设P(G,λ)是图G的色多项式,如果对任意使P(G,λ)=P(H,λ)的图H都与G同构,则称G是色唯一图。这里通过比较图的特征子图的个数,讨论了由Koh和Teo在文献[1]中提出的问题(若|ni-nj|≤2,1≤i,j≤t且min{n1,n2,…,nt}充分大,K(n1,n2,…,nt)是否为色唯一图?)。证明了,若|ni-nj|≤2且∑ti=1ni>t22+t t-1,则K(n1,n2,…,nt)是色唯一图;若ai=0或k,∑ti=1n+ai>t28k2+|t2k|t-1,则K(n+a1,n+a2,…,n+at)是色唯一图。其条件比文献[4]中的条件较好一些。

完全t部图K(n-k,n-2,n,…,n)的色唯一性

文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。

完全t部图的色唯一性

设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;这里通过比较t部图的t+1色类的划分数,证明了若min1≤i≤t{n+ai}≥1/2(a12+a22+…+at2)-1/2t(a1+a2+…+at2)+1,则完全t部图K(n+a1,n+a2,…,n+at)是色唯一图;若n≥(t-1)/2t(k2+v2)+1/tkv+v+1,v≥0,k≥-v,则完全t部图K(n-v,n,n+k,n,…,n)是色唯一的。

关于完全t部图的色等价性(英文)

设K（n1，n2，…，nt）表示完全t部图，K(n1，n2，…，nt）－A表示从K（n1，n2，…，nt）中删去子边集A所得之图．本文证明了：令G＝K（n1，n2，…，nt），J为整数集，R为实数集．设简单图Y满足Y～G，则且进一步有：若s＞0且αi∈R（i＝1，2…．t）．

完全多部图的点被多重集可区别的IE-全染色

利用反证法,构造染色法,色集合事先分配法,讨论了完全t部图的顶点被多重集可区别的IE-全染色。 给出了最优染色的一个方案,并确定了相应染色的色数。 完全解决了完全多部图的点被多重集可区别的IE-全染色的问题。

完全图K_n和完全多部图K_n(t)的｛C_3,S_4｝-强制分解

本文给出完全图Kn 和完全多部图Kn(t)存在｛C3 ,S4｝

关于几类图的Fractional全控制数

设G=(V,E)是一个无孤立点的图,一个实值函数f:V→[0,1]满足∑v∈N(u)f(v)≥1对一切u∈V(G)都成立,则称f为图G的一个Fractional全控制函数。图的Fractional全控制数定义为γ0f()G=min{f(V)|f为图G的Fractional全控制函数},文章中研究了图的Fractional全控制问题,主要给出了关于联图的Fractional全控制数的一个上界,由此确定了几类特殊图的Fractional全控制数,并推广了部分已知结果。

非线性规划在证明不等式中的应用(英文)

我们在讨论完全t部图的色等价问题时 ,需要确定变量 αt =-lTQB 在约束 ( β+b) TB( β+b) <α2 t 下的变化范围 ,其中αt ∈R ,l ,b ,β∈Rt-1 ,Q ,B∈R(t-1 )×(t-1 ) (αt,l,b ,Q ,B)的定义见正文中的定理 ) .我们利用非线性规划的方法 ,证明了如下不等式 :ct-dt-1 at<αt <ct+dt-1 at,其中dt-1 =2 (t - 1) /t,ct = t- 1i=1(ni-nt) /t .