非连通图C2n+1∪Gn-1的优美性

证明了非连通图C2n+1∪Gn-1是优美图,其中C2n+1是有2n+1个顶点的圈,Gn-1是任意一个有n-1条边的优美图。     

图的集控制数

设图Ｇ＝（Ｖ，Ｅ）．一子集Ｄ包含于Ｖ，若对每一个Ｘ包含于Ｖ－Ｄ，都存在一个非空子集合Ｙ包含于Ｄ，使得由Ｘ∪Ｙ所导出的子图（Ｘ∪Ｙ）连通，则称Ｄ为Ｇ的一个集控制集（ｓｄ－集）。Ｇ的集控制数ｙ２（Ｇ）是Ｇ的一个集控制集的最小基数。本文给出了集控制集一个充要条件，并讨论了生成子图与补图的集控制数。     

若干多重联图的邻点可区别E-全染色

G（V,E）是一个简单图,忌是一个正整数,f是一个V（G）∪E（G）到{1,2,…,k}的映射．如果任意uv∈E（G）,则f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,C（u）≠C（v）,称,是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数．本文给出了扇与星、路、圈间的多重联图的邻点可区别E-全色数．其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}．     

关于图的反符号圈控制数

摘要：引入了图的反符号圈控制的概念,设G=（V,E）是一个非空图,一个函数f：E→{＋1,-1}对G中每一个无弦圈C均有∑e∈E（G）f（e）≤0成立,则称厂为图G的一个反符号圈控制函数,而γ′rsc（G）=max{∑e∈E（G）f（e）｜f为图G的反符号圈控制函数｜称为图G的反符号圈控制数。给出了图的反符号圈控制数的界限,刻画了满足γ′rsc（G）=-｜E（G）｜＋2的所有连通图G,并且确定了图与补图以及几类特殊图的反符号圈控制数。     

串图的边色数

设G（V,E）为连通简单图,V（G）={v10,v20,…,vp0}.M(G,n)称为G的n级串图,其中V（M（G,n))={vij|i=1,2,…,p;j=0,1,…,,n},E(M(G,n))={vjkvjk|i=1,2,…,n;0≤k≤n,且vi0vj0∪E（G）}∈{vijvij 1|i=1,2,…,p;j=0,1,…,n-1}。证明了对于n≥1,M(G,n)的边色数为其最大度△（M（G,n））。     

图Km,UKnUKp的优美性

得到了图Ｋｍ∪Ｋｎ∪Ｋｐ是优美图的充分必要条件。     

联图Pm∨Sn，n的邻点可区别全染色

简单连通图G（V,E）的k-正常全染色,称为邻点可区别的,如果对G（V,E）的任意相邻两顶点,其顶点的颜色及关联边的颜色构成的集合不同。这样的k中最小者称为G（V,E）的邻点可区别全色数。研究了路与双星图的联图Pm∨Sn,n邻点可区别的全染色问题,得到了联图Pm∨Sn,n邻点可区别的全色数。     

图Pm∨Wn与Wm∨Wn的第一类弱全色数

对简单图G（V,E）,f是从V（G）∪E（G）到{1,2,…,k}的映射,k是自然数,若f满足（1）uv∈E（G）,u≠v,f（u）≠f（v）;（2） uv,uw∈E（G）,v≠w,f（uv）≠f（uw）;则称f是G的第一类弱全染色.给出了路与轮,轮与轮联图的第一类弱全色数.     

C23n,C24n邻点可区别的全染色

设G(V，E)是阶数不小于2的简单连通图，n是自然数，V∪E到{1，2，…，k}的映射f满足Vuv∈E(G)，f(u)≠f(v)，f(u)≠f(uv)≠f(v)；А↓uv,uw∈E(G),(v≠w)，f(uv)≠f(uw)；А↓uv∈E(G),G(u)≠C(v)．其中C(u)=f(u)∪{f(uv)|uv∈E(G)}．，f称为G(V,E)的一个邻点是可区分的全染色法，简记为k-AVDTC.其中最小的k称为G的邻点可区别的全色数。G^2是G再加上G中点间距离为2时连边后的图．本文得到了3n、4n阶圈C3n^2，C4n^2邻点可区别的全色数。     

关于图的符号边控制数

设G为一个n阶连通图，m=|E(G)|，△和δ分别为图G的最大度和最小度，给出了图G的符号边控制数的一个下界、即γ‘‘‘‘‘‘‘‘，（G）≥[M-(△-δ)(△-2)(n-δ)/2△-1]，并确定了几类特殊图的符号边控制数。     

关于集控制集的若干结论

设图Ｇ＝（ＤＶ，Ｅ）。一子集Ｄ包含于Ｖ，若对任何Ｘ包含于Ｖ－Ｄ，都存在一个非空子集Ｙ包含于Ｄ，使得导出子图＜Ｘ∪Ｙ＞连通，则称Ｄ为Ｇ的集控制集。Ｇ的集控制数γｓ（Ｇ）是Ｇ的集控制集的最小基数。本文讨论了割点属于Ｇ的任一最小集控制集的必要条件，并且给Ｇ有独立集控制集的充要条件。     

三色拉姆塞数R_3（C_8）研究

用r种颜色对图G的所有边着色,记着第i色的边构成的子图为Gi,如果存在一种着色方法使得每一个Gi（1≤i≤r）都不包含图H,则称图G对于H可以r着色.拉姆塞数Rr（H）是使得完全图Kn对于H不可以r着色的最小正整数n.令Cm表示长度为m的圈,Dzido等证明了R3（C2k）≥4k.本文对k=4的情形进行研究,利用计算机,通过大量的计算证明了R3（C8）=16.     

S0＋Fn与S1＋Fn的邻点强可区别全色数

设G(V,E)是阶数不小与3的简单连通图,k是自然数,f是从V(G)(U) E(G)到{1,2,…,k)的映射,满足对任意的uv∈E(G),f(u)≠f(u),f(u)≠f(uv)≠f(v);对任意的uu,uw∈E(G),u≠w,f(uv)≠f(uw);对任意的uv∈E(G),C(u)≠C(v),其中C(u)={f(u)}U{f(v)|uv∈E(G)}U{f(uv)|uv∈E(G)}则称f是图G的一个邻点强可区别的全染色法.简记作k-AVSDTC,且称Xast(G)=min{k|G的所有k-AVSDTC}为G的邻点强可区别全色数.本文得到了星与扇联图的邻点强可区别全色数.     

Faudree猜想与Hamilton性

Ｆａｎｄｒｅｅ，Ｇｏｕｌｄ和Ｊａｃｏｂｓｏｎ等人在１９８９年曾提出的如下猜想：如果Ｇ是ｎ阶２－连通图，δ（Ｇ）≥ｔ，任意ｎ，ｖ∈Ｖ（Ｇ），且ｕｖ∈Ｅ（Ｇ），／Ｎ＊ｕ）∪Ｎ（ｖ）／≥ｎ－ｔ＋１，则一点泛圈图，文中证明了这个猜想，还得到了条件相近的另一结果。     

一些图C4k∪Pn的优美性

证明了C4k∪Pn当n=k 2,2k 1,2k 2,2k 3,3k,3k 1时的优美性.     

关于Ulam猜想的部分结果和Czh+1∪nK2的对角Ramsey数

证明了n=7时的重构猜想,给出p(p≥7)阶图G的p个主子图G1,G2,…,Gp.其中G1,G2,…,G6中的点v1,v2,…,v7未标定,点v8,v9,…,vp标定;G7,…,Gp中的点全不标号,则G可由G1,G2,…,Gp在同构意义下惟一重构.还证明了Czh 1∪nK2的对角R am sey数为R(Czh 1∪nK2)=m ax{3(h n) 1,4h 1}.式中h,n∈Z且h≥2,n≥1.     

3-边连通图与4-匹配

设G是阶为n的3-边连通简单图,M4是G的一个4-匹配,设∑（M4）表示和M4关联的8个顶点的度数和。本文证明了：若对G的每个4-匹配M4有,∑(M4)≥2n 3,则G是可折的或者G是Petersen图。     

奇数阶完全图的因子分解与对称群

F．Harary在[1]中提出如下一个未解决问题：那些有限置换群是完全图同构分解的因子对称群？对于n〉1。构造了2n＋1阶完全图G的／7,个不同的同构分解G^e=G1∪G2∪…∪Gn,其中G1是2n个点的路的第e对对称点和另1个点连接得到的图。证明了G的同构分解的因子对称群是n阶循环群。     

关于图的反减圈控制数

设G=（V,E）是一个图,C为G的导出圈,函数厂：E→｜＋1,0,-1｜,如果对任意e∈E（C）均有∑f（e）≤0成立,则称f为图G的一个反减圈控制函数,称ymc（G）=max{∑f（e）｜f为G的反减圈控制函数,e∈E（G）}为图G的反减圈控制数．本文给出了图的反减圈控制数的上界和极大平面图及几类特殊图的反减圈控制数．     

树的二分全优美标号

一个有q边的连通图G的一个标号是一个映射f,使得图G顶点分配给不同的整数,如果图G的所有边标号集等于{1,2,…,q},则称f是图G的一个优美标号,称G是优美图.图的优美标号可用于解决Rosa分解猜想,这就需要证明每一棵树是优美的,然而它又成为一个未解决的难题.已知树的二分全优美标号可得到一些逼近优美树猜想的结果,因此可考虑一个弱于优美树猜想的猜想:一棵被删除所有叶子后余图恰是一棵毛毛虫树的树T是二分全优美的.树T的一个二分标号是一个双射f,且存在一个正整数k,使得f(u)≤k≤f(v),则顶点u和v属于树T的顶点集的二部分划分的不同部集.定义了全优美标号空间和k?二分全优美树,证明了一类二分全优美树,给出一些大型二分全优美树的构造方法.