关于St^n∪i=1 mi-C4的优美性

本文就星形树与m—C4并图的优美性进行探讨，证明了当m≥2这类图Stp∪m—C4是优美图．并对星形树St与^n∪i=1 mi-C4并图St^n∪i=1 mi-C4的优美性进行探讨.证明了当max mi≥3 i=1，2……，n这类图St^n∪i=1 mi-C4是优美图.     

蕴含K3∪K4的可图序列（英文）

对于给定的图H,若存在可图序列π=（d1,d2,…,dn）的一个实现包含H作为子图,则称π为蕴含H-可图的.本文给出了可图序列π=（d1,d2,…,dn）蕴含K3∪K4可图的一个充分条件,其中K3∪K4是恰好有一个公共顶点的K3和K4的并图.     

关于P3n∪＜C4,3＞图的优美性

讨论了非连通并图P3n∪＜C4,3＞的优美性,用构造性的方法给出了P3n∪＜C4,3＞的优美标号.     

一类图中具有最小能量的图

设λ1,λ2,…,λn是图G的特征值,则称E(G)=|λ1| |λ2| … |λn|为图G的能量.用Sl1n,l2表示由两个具有唯一公共顶点u的圈Cl1和Cl2,且其余边均为u上的悬挂边的n阶双圈图.利用Sachs子图证明了在所有含有两个边不相交的圈Cl1和Cl2的n阶双圈连通图中Sl1n,l2是能量最小的.     

关于P3n∪＜C4,3＞图的优美性

讨论了非连通并图P3n∪＜C4,3＞的优美性,用构造性的方法给出了P3n∪＜C4,3＞的优美标号.     

一类双图图中具有最大、最小Wiener指数的图

设G=（V,E）是一个连通图,G的Wiener指数W（G）是指图G中所有顶点对之间的距离之和,即W（G）=∑{u,v}GdG（u,v）.B（n）表示具有n个顶点和n＋1条边的简单连通双圈图的集合,B1（n）表示B（n）中圈之间没有公共边的双圈图的集合.刻画了B（n）和B1（n）中具有最小Wiener指数和具有最大Wiener指数的极图的特征.     

一类双圈图中具有最大、最小Wiener指数的图

设G=(V,E)是一个连通图,C的Wiener指数W(G)是指图G中所有顶点对之间的距离之和,即W(G)= ∑∣u,v∣(∈) GdG(u,v).B(n)表示具有n个顶点和n 1条边的简单连通双圈图的集合,B1(n)表示B(n)中圈之间没有公共边的双圈图的集合.刻画了B(n)和B1(n)中具有最小Wiener指数和具有最六Wiener指数的极图的特征.     

一类满足α（H）=4的非树图

用C(H)表示图H的中心,”■”表示图同构,定义图参数文[2]和[3]构作了某些满足α=3的图,解决了α=3的图的存在问题,本文构作了一类满足α=4的图,解决了α=4的非树图的存在问题。令n和m都是自然数。设H是一个图,d(H)=d_H(x_1,x_2)=2m-1.H=(∨(H),E(H)),其中定理令n>m.若H满足A.(?)u∈∨(H),有d_H(u,x_1)+d_H(u,x_2)≤2m;B.存在v_0∈(H),使d_H(v_0,x_1)+d_H(v_0,x_1)=2m;C.不存在v∈(H),使d_H(v,x_1)=d_H(v,x_2)=m。则α(H)=4。     

αCP（a）∪βCP（b）类整谱图

设图G是一个简单图,图G的补图记为G,如果G的谱完全由整数组成,就称G是整谱图.鸡尾酒会图G=CP（n）=K2n-nK2（K2n是完全图）是整谱图.确定了图类αCP（a）∪βCP（b）中的所有整谱图.     

由圈长分布确定的偶图

阶为n的图G的圈长分布是序列(c1,c2,…,cn),其中ci是图G中长为i的圈数.得到如下结果:设A■E(Kn,r),|A|=4,n≤r≤m in{n 6,2n-9},则G=Kn,r-A是由它的圈长分布确定的.     

蛛网图的连通包数

证明了蛛网图W （m ,n）的连通包数为hc （W （m ,n））＝ m＋2 n -1．通过对蛛网图进行简化处理,即将蛛网图W （m ,n）的叶子顶点去掉,得到图G的连通包数为hc （G）＝┌n2┐＋ m ．     

关于柱图Cλ(Pn)的细分图的k-优美性

一个简单图G=(V,E)是k-优美的(k≥1为整数),如果存在单射f:V(G)→{0,1,2,…,｜E｜+k-1}使得对所有的边uv∈E(G),由f*(uv)=｜f(u)-f(v)｜导出的映射f*:E(G)→{k,k+1,…,｜E｜+k-1}是双射.若G是简单图,且在G的所有相邻的两个顶点之间都加入一个顶点,则所得到的图称为G的细分图,该文证明了当λ≥2,n≡0(mod2)时,Cλ(Pn)的细分图Cλ(Pn)是k-优美图.     

关于积图Ps×Ct的细分图的K-优美性

该文定义:一个简单图G=（V,E）是k-优美的（k≥1为整数）,如果存在单射f:V（G）→{0,1,2,…,|E| k-1}使得对所有的边uv∈E（G）,由f＊（VV）一丫（V）-/（V门导出的映射 f＊:E（G）→{k,k 1,…,|E| k-1}是双射。若G是简单图,且在G的所有相邻的两个顶点之间都加入一个顶点,则所得到的图称为G的细分图。该文还证明了积图Pn×C2m、P2n×C2m 1、P2n×Cm的细分图是k-优美图。     

关于图P_n~3∪_4的优美性

讨论了形如P_(n³)U_4非连通并图的优美性,用构造性的方法给出了P_(n3)U_4非连通并图的优美性,用构造性的方法给出了P_(n³)U_4的优美标号,并证明P_(n3)U_4的优美标号,并证明P_(n³)U_4是交错图.     

关于图P_(6k)~3∪P_n~3的优美性

讨论了P_(6k)~3∪P_n~3非连通并图的优美性,用构造性的方法给出了P_(6k)~3∪P_n~3的优美标号,并证明P_(6k)~3∪P_n~3是交错图.     

一类图自映射的周期集

设G是由两个圆圈和一线段组成的图,有唯一的分支点o和端点pe.该文证明:设f:G→G是G上连续映射且f(o)=o,per(f)∩{1,2,…,n}={1,n},其中n>5,则f的周期集或为{1,n,n 1,n 2,…};或为{1,n,n 2,n 4,…当n是偶数;或为{1,n,n 2,n 4,…∪{2n 2,2n 4,2n 6,…当n是奇数.相反地,如果A(n)(n>5)是上述三种集合之一,则存在G上的连续自映射f使得f(o)=o且Per(f)=A(n).     

与图的顶点染色数有关的几个问题

设c(G)是无向简单图G(V,E)的顶点染色数,证明了:若︱S︱p/2且︱S︱=p-m,则图G不存在第p-q类图,其中:q≥2m+1,m≥3且m∈Z~+;若︱S︱=p-4,则小x(G)≤p-3;若︱S︱=p-4,则x(G)≤4■(G)+■2(G)-1.     

P2r,4m＋2图（r=8,10）的优美性

设u、v是两个固定顶点,用b条内部互不相交且长度皆为a的道路连接u、v所得的图用Pa,b表示.K.M.Kathiresan证实P2r,2m-1（r,m皆为任意正整数）是优美的,且猜想：除了（a,b）=（2r-1,4m-2）外,所有的Pa,b都是优美的.杨元生教授已证实P2r-1,2m-1是优美的,并且证实了当r=1,2,3,4,5,6,7,9时P2r,2m也是优美的.该文证实当r=8,10时P2r,4m＋2也是优美的.     

花图的邻点可区别关联色数

轮Wr+1(r≥3)是一个r阶圈加上一个新的顶点,再把圈上每个顶点与新顶点连上边所得到的图,新顶点与圈上顶点之间的边称为辐边,圈上的边称为边缘边。所谓花图Fr,m,n(r≥3,m≥1,n≥2m+1)是在轮Wr+1中,在每条辐边上分别嵌入m-1个新点,在每条边缘边上分别嵌入n-2m-1个新点所得到的图。研究花图Fr,m,n(r≥3,m≥1,n≥2m+1)的邻点可区别关联着色,确定了部分花图的邻点可区别关联色数,并给出了剩余花图的邻点可区别关联色数的上界。     

度和,邻集并与Hamilton图

证明如下结果：设Ｇ是阶ｎ的２连通图，若对Ｇ的任意两个不要邻的顶点ｎ和ｖ，都有ｄ（ｕ）＋ｄ（ｖ）≥ｎ－１或／Ｎ∪Ｎ（ｖ）／≥ｎ－δ－１，则Ｇ是Ｈａｍｉｌｔｏｎ图，除非Ｇ属于一类特殊图，δ表示Ｇ的最小度。