完全三部图K2,2,r,r=4,5,6,7,不是U3LC图

M.Ghebleh和E.S.Mahmoodian在其开放问题中提出了完全三部图K2,2,r,r=4,5,6,7,是U3LC图还是具有M(3)性质这样一个问题。在这篇文章中我们叙述并证明了图K2,2,7具有M(3)性质这样一个主定理,进一步证明了图K2,2,r,r=4,5,6,也具有M(3)性质。     

完全三部图K2，2，r，r=4，5，6，7，不是U3LC图

M.Ghebleh和E.S.Mahmoodian在其开放问题中提出了完全三部图K2,2,r.r=4,5,6,7,是U3LC图还是具有M(3)性质这样一个问题.在这篇文章中我们叙述并证明了图K2,2,7具有M(3)性质这样一个主定理,进一步证明了图K2,2,r,r=4,5,6,也具有M(3)性质.     

K1＊4，5，K1＊4，4，K2，2，4和K2,2,5不是U3LC图

笔者针对M.Ghebleh和E.S.Mahmoodian的一个关于列表染色图的猜想做了部分解决,证明了K1*4,5,K1*4,4,K2,2,4和K2,2,5不是U3LC图,而且它们的m数都是3.     

完全多部图的M(5)性质

针对完全多部图的唯一列表染色问题进行了研究，证明了对任意正整数n，图K1＊7，n，K1＊n，7都具有M（5）性质。     

风车图K_3~（（n））的[r,s,t]-着色

研究了风车图K3（n）的[r,s,t]-着色问题,给出了风车图K3（n）在一定条件下的[r,s,t]-色数.     

二部图的[r，s，t]-着色

给出了二部图G的[r，s，t]-色数的界及它达到下界时的条件，讨论了星作为特殊二部图的[r，s，t]-色数，得到的结果为若G是二部图，任意v1，v2∈V△，v1v2 （∈/）E（G），任意u∈V△， u1∈NG（u），使得dG（u1）=1，且s≥2t，r≤t，则χr,s,t（G）=（△-1）s＋1；若G是二部图，且r≥（△-1）s＋2t，则χr,s,t（G）（G）=r＋1；若G是二部图，且（△-1）s＋t〈r≤（△-1）s＋2t，则χr,s,t（G）≤（△-1）s＋2t＋1；若G是二部图，则r△＋1≤χr,r,r（G）≤r（△＋1）＋1。     

关于完全s部整图

F.Harary和A.J.Schwenk(Lecture Notes in Mathematics.Berlin:Springer-Verlag,1974,406:46-51.)提出了整图的概念,即当无向图G的邻接矩阵A的特征值都是整数时,G称为整图.目前,人们已经研究了n类简单整图的性质,并得到了一些有趣的结果.运用线性代数方法证明了两个结论:设r,r1,r2,s是正整数,那么:1)完全s部图K(r,r,…,r)是整图;2)完全2部图K(r1,r2)是整图的充要条件是r1r2为完全平方数.     

两类图的和数

研究了两类完全多部图的和数，证明了图K1，1，r和K1，1，1，r（r≥3）的和数分别是r和r＋2．     

H（r,s）的补图色性

设Pr和Ps分别是两条具有r和s个顶点的路,用K3连接Pr和Ps的两个起点所得到的图,记作H（r,s）。h(G,x）是图G的伴随多项式。作者证明了,如果Pr-1,Ps-1和H（r,s）是不可约的,并且r和s是偶数（r,s≥4）。则H(r,s)的补图是色唯一的。同时还给出了计算伴随多项式的基本公式。     

一类变换图的递归构造方法

1980年,著名的图论专家R.A.Brualdi提出了关于变换图G（R,S）直径的Brualdi猜想[1],但至今仍悬而未决.J.Jin于2011年定义了一类变换图G（R＊,S＊）[2],其中,R＊=（r1,r2）且S＊=（1,…,1）.本文根据G（R＊,S＊）中最大团的性质找到G（R＊,S＊）的递归构造方法.     

基本集的邻域交与无K1,r^—图的可迹性

通过对图的基本集的研究，得到无Ｋ１，ｒ＾－图是可迹的几个充分条件。     

超图的[r,s,t]-着色

将一般图的[r,s,t]-着色推广到超图上得到超图的[r,s,t]-着色的定义及超图[r,s,t]-着色的一些性质和定理,并讨论了超图的[r,s,t]-色数的上下界。     

关于完全多部图Kn(t)的{C3,C5}-强制分解

关于完全多部图Kn(t)的Ck 分解 ,已经取得了一系列的研究成果。Kn(t)的 {Ci,Cj} 强制分解则是指Kn(t)分解为长为i或j的圈 ,并且分解中至少各有一个长分别为i和j的圈。本文证明了多部图Kn(t)的 {C3,C5 } 强制分解存在的必要条件也是充分的。     

L*n,p图的全匹配数

设Kp是p阶完全图。 取Kp的任意r个顶点分别点粘接r颗树,所得到的n阶图集记为L*n,p。 确定了L*n,p中具有最大和最小,第二大和第三大全匹配数的图。     

图Dm,4的[r,s,t]-着色

由m个四回路恰有一个公共点构成的图记为Dm,4。研究图Dm,4的点着色、边着色和全着色,给出图Dm,4在参数r,s,t满足一定条件时的[r,s,t]-色数。     

关于P_(2r,2s-1)的k-优美标号

对于简单图G=,如果存在一个映射f:V(G)→{0,1,2,…,|E|+k-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(u)|u∈V}=|E|+k-1;3)对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),且{g(e1)|e∈E}={k,k+1,…,|E|+k-1},g(e2)=|f(u)-f(v)|,e=uv,则称G是k-优美图,f称为G的k-优美标号.作者研究了一类图的k-优美标号.