图的边添加和减少

用P（t,d）（或者C（t,d））表示从一条长为d的简单路（或者简单圈）通过添加t条边后得到图的最小直径.证明了：如果t和d满足条件t≥4且t＋4≤d≤t＋7,或者t=4且d=10k＋1（k≥1）,那么P（t,d）=[d-2D＋1]＋1.对某些t和d,确定了C（t,d）的值和最好下界,部分地解决了Schoone等的猜想[J.GraphTheory,1987,11：409-427].     

无向路的添加边问题

对于n个节点的无向路pn,令p(n,t)为pn中添加t条边后得到的变更图的最小直径.本文通过构造出一类变更图,改进了p(n,t)的上界.     

图中度和与基本独立集(英)

设G是一个图，p（G）和c（G）分别表示G中最长路的阶和最长圈的阶.本文将证明如果G是连通图且。σ3（G）≥n，那么或者G包含一条Hamilton路或者c（G）≥p（G）－1．     

变更图的边添加

证明了:对任何整数t≥6和d≥2,从一条长为d的简单路通过添加t条边后得到的图的最小直径上界为[d-2/t 1] 2,如果d∈J'(t,k)={2k(t 1) 1,2k(t 1) 2,2k(t 1)-t 1}∪{2k(t 1)-t h:h=6,7,…,t};其他情形为[d-2/t 1] 1.这个证明改进了已知结果,而且[d-2/t 1] 1是最好的上界.     

不含3圈的平面图的无圈边染色

图的无圈边染色是图的染色理论中的一个重要问题,2001年,Alon等猜想任意简单图G的无圈边色数都不超过△（G）＋2,其中△（G）为图G的最大顶点度。为了研究该猜想对平面图是否成立,利用差值转移方法,证明了不包含三角形的平面图G的无圈边色数不超过△（G）＋3．     

三路树P（2m,2m,2m）是边幻图的证明

令简单图G－（V，E）是有p个顶点q条边的图，假设G的顶点和边由1，2，3，，…，p q所标号，且f:VUE→{1,2,…，p q}是一个双射，如果对所有的边xy,f(x) f(y) f(xy)是常量，则称图G是边幻图（edge-magic)，文[1]中猜测树是边幻图，本文证明了三路树P（m,n,t）当m,n,t为偶数且相等时为边幻图。     

关于图中有三个边不相交的圈

本文得到了：若ε（G）≥v（G）＋11，则图G有三个边不相交的圈．     

1-树与外平面图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对1-树与外平面图成立，且它们的色数均不超过最大度加1。     

Halin图的无圈边着色

设f是图G的一个正常边着色，若在f下G中没有2-色圈，则称f是图G的一个无圈边着色，其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图，无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立，且当Δ≤4时，其色数不超过5；当Δ≥5时，其色数等于最大度。     

两类笛卡尔积图的关联色数

Ｒｉｃｈａｒｄ Ａ． Ｂｒｕａｌｄｉ 和 Ｊ． Ｑｕｉｎｎ Ｍａｓｓｅｙ 在［１］ 中引入了图的关联色数,并且提出了关联色数猜想,即：每一个图 Ｇ 都可以用Δ（ Ｇ） ＋ ２ 种色正常关联着色。本文的主要结果如下：我们不仅证明了路与路、路与圈的笛卡尔积图满足关联色数猜想,进而确定了它们的关联色数。     

关于图的边添加

给定任意正整数t和d(≥2),记P(t,d)为在直径d的路上加上t条边后所得图的最小直径.证明了:P(6,4)=1; 当d=5,6,7时有P(6,d)=2;当d=7(2k-1)+h(k≥1, 1≤h≤14) 时有(d)/(7)≤P(6,d)≤ (d)/(7)+2若h=7;(d)/(7)+1其他;当d=5,6,7,8时有P(7,d)=2;当d=8(2k-1)+h (k≥1,1≤h≤16)时有(d)/(8)≤P(7,d)≤ (d)/(8)若h=1;(d)/(8)+2若h=2,3,4,5,6,7,8;(d)/(8)+1其他.     

收缩临界6连通图中的6度顶点

如果6连通图的一条边收缩后使得所得到的图仍是6连通,则这条边称为6可收缩边.一个不包含6可收缩边的非完全图被称为收缩临界6连通图.由Egawa的结果可知收缩临界6连通图中有6度点.设G是收缩临界6连通图,用V6表示G中6度点的集合.Ando等人通过证明存在常数c使得|V6|＞c|V(G)|且c≥(1)/(7).现将这一常数改进为c≥(1)/(5).     

无向广义De Bruijn图的m-限制边连通性

m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm（G）.对于包含m-限制边割的连通图G,有λm（G）≤ξm（G）（m≤3）;如果λm（G）=ξm（G）,则称图G是极大m-限制边连通的.本文证明：当n≥7时,无向广义De Bruijn图UBG（2,n）是极大m-限制边连通的（m={2,3}）.     

优化正则图的限制边连通性的最小度条件

限制边割将连通图分离成不合孤立点的不连通图，如果最小限制边割只能分离孤立边，则称图G是超级限制边连通的．证明了如果k＞|G|/2 1，那么k正则连通图G是超级限制边连通的，k的下界在一定程度上是不可改进的．     

关于判定超欧拉图的收缩法

P.A.Catlin提出一个问题：设H是图G的一个连通子图，如果G关于H的收缩图G/H有一个欧拉生成子图，那么在什么条件下G也有一个欧拉生成子图？研究了这一问题，讨论了Catlin提出的用收缩法判定超欧拉图的两个定理，给出了一些实用的超欧拉图的判别方法。     

3正则3连通图的转发指数

n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G, Fernandez de la Vega和Manoussakis [Discrete Applied Mathematics, 1989, 23(2):103-123]证明ξ(G)≤(n-1)·[(n-k-1)/k]和π(G)≤n[(n-k-1)/k],并且猜想ξ(G)≤[(n-k)(n-k-1)/k].我们分别改进了ξ(G)≤(n-1)[(n-k-1)/k]-(n-k-1)和π(G)≤n[(n-k-1)/k]-(n-k),并且证明了猜想对k=3的情形.     

几类特殊图的一般指标集

令G=(V(G),E(G))为一简单连通图,V(G)和E(G)分别是图G的顶点集和边集.一个顶点标号函数f:V(G)→Z2诱导出一个边标号函数f*:E(G)→Z2,其中?v1 v2∈E(G),有f*(v1v2)=f(v1)+f(v2).当标1和标0的顶点数相差m(m<|V(G)|)时,标号为1和0的边数差的集合称为图G...     

广义Mycielski图的边色数

设μ1(G)表示一个图G的Mycielski图.广义Mycielski图μm(G)是Mycielski图μ1(G)的自然推广.研究广义Mycielski图μm(G)的边染色问题,运用换色技巧证明了:若G是不同于K2的连通简单图,则对任何m≥2,μm(G)是第一类的,即边色数等于最大度.推广了现有关于Mycielski图的边色数的相关结果.