A′da′m循环图

若对任意的与ｎ互素的整数λ，都有〈λｊ＿１，λｊ＿ｒ，…，λｊ＿ｒ〉＝〈ｊ＿１，ｊ＿２，…，λ＿ｒ〉，则称循环图Ｃ＿ｎ〈ｊ＿１，ｊ＿２，…，ｊ＿ｒ〉为Ａ′ｄａ′ｍ循环图。本文给出了一个循环图Ｃ＿ｎ〈ｊ＿１，ｊ＿２，…ｊ＿ｅ〉为Ａ′ｄａ′ｍ循环图的充要条件以及ｎ阶Ａ′ｄａ′ｍ循环图的个数的计算公式。     

图的升分解问题的两个新结果

Ａｌａｖｉ等人在１９８７年定义了图的一种新分解,即“升分解”（ＡｓｃｅｎｄｉｎｇＳｕｂｇｒａｐｈＤｅｃｏｍｐｏｓｉｔｉｏｎ）,并且猜想：任意有正数条边的图都可升分解．该文证明了下面两个新结果：（１）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｎ＋１≤ｉ≤２ｎ－２ｎ／３［］２－２时,Ｇ＝Ｋｎ－Ｈｉ可升分解为Ｋ１,１,Ｋ１,２,…,Ｋ１,ｎ－５,Ｋ１,ｎ－４,Ｇｎ－３（ｎ≥６）,其中Ｋ１,ｎ－４Ｇｎ－３．（２）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｉ≥２ｎ－２ｎ／３［］２时,Ｇ＝Ｋｎ－Ｈｉ不一定有定理１形式的升分解．     

与几类子图2-正交的(g,f)-因子分解

设ｇ和ｆ分别是定义在图Ｇ的顶点集合Ｖ（Ｇ）上的整数值函数且对每个ｘ∈Ｖ（Ｇ）有ｇ（ｘ）≥２。本文证明了：若Ｇ是一个（ｍｇ＋ｍ－１,ｍｆ－ｍ＋１）－图,则对于Ｇ中任意给定的子图２Ｋ１,ｍ或２ｍ－星或２ｍ－对集,Ｇ有一个（ｇ,ｆ）－因子分解与之２－正交。     

循环图带宽的上界

给出了连通循环图Ｇ＝Ｃｎ〈ｊ１,ｊ２,…,ｊｒ〉带宽Ｂ（Ｇ）的上界,即Ｂ（Ｇ）≤２ｊｒ,并研究得到了四度连通循环图Ｇ１＝Ｃｍ１ｍ２〈ｋ１ｍ１,ｋ２ｍ２〉的带宽Ｂ（Ｇ１）＝２ｍｉｎ（ｍ１,ｍ２）（ｍ１＝ｇｃｄ（ｍ１ｍ２,ｊ１）,ｍ２＝ｇｃｄ（ｍ１ｍ２,ｊ２））,及五度连通循环图Ｇ２＝Ｃｍ１ｍ２〈ｊ１,ｊ２,ｍ１ｍ２／２〉的带宽Ｂ（Ｇ２）＝４ｍｉｎ（ｍ１,ｍ２）（２ｍ１＝ｇｃｄ（ｍ１ｍ２,ｊ１）,２ｍ２＝ｇｃｄ（ｍ１ｍ２,ｊ２））．     

图的正交因子分解

研究了图的正交因子分解问题．设ｋ１,…,ｋｍ是正整数,Ｇ是［０,ｋ１＋…＋ｋｍ－ｍ＋１］－图,Ｈ是Ｇ的任一有ｍ条边的子图．若｜Ｖ（Ｈ）｜≥｜Ｅ（Ｈ）｜＝ｍ,则图Ｇ有一个［０,ｋｉ］ｍ１－因子分解与Ｈ正交     

一类图色唯一的一个充要条件

讨论了形如（Ｐｔ１∪Ｐｔ２∪…∪Ｐｔｓ）∪（Ｃｍ１∪Ｃｍ２∪…∪Ｃｍｔ）∪Ｄｎ一类图的补国的色性，并给出了其补图色唯一的一个充要条件。     

一个关于2—连通图周长的次条件

设Ｇ为ｎ阶２－连通图，顶点ｖ１，ｖ２，…，ｖｎ满足ｄ≤ｄ２≤…≤ｄｎ，其中ｄｉ＝ｄ９ｖｉ），ｉ＝１，２，…，ｎ。给出ｃ（Ｇ）≥ｍｉｎ「ｎ，ｍ」的如下条件：ｊ〈ｋ，ｖｊｖｋ∈Ｅ，Ｊ＋Ｋ〈ｍ，ｄＪ≤Ｊ，Ｄｋ＋１≤ｋｄ（ｖ），ｄ（ｕ）≤Ｊ（其中Ｊ＝ｄ（ｖｊ），Ｋ＝ｄ９ｖｋ））｝→ｄｉｓｔ（ｖ，ｕ）≠２。     

一类图色唯一的一个充要条件

讨论了形如（Ｐｌ１∪Ｐｌ２，∪…∪Ｐｌｓ）∪（Ｃｍｌ∪Ｃｍ２∪（Ｃｍ２∪…Ｃｍｔ）∪Ｄｎ一类图的补图的色性，并给出了其补图色唯一的一个充要条件。     

关于完全二分图的整和数的研究

提出了正整数的真ｒ－剖分的定义并利用它解决了１９９４ 年Ｆ．Ｈａｒａｒｙ 在［３］中提出的一个未决问题,即确定完全二分图Ｋｒ,ｓ的整和数和和数．得到如下结果：σ（Ｋｒ,ｓ）＝ ζ（Ｋｒ,ｓ）＝ ｓｋ＋ ｒ－ １,其中ｓｒ２,ｓｋ 是整数ｓ的真ｒ－剖分的最末项。此外,在这篇文章中我们还举例说明了Ｎ．Ｈａｒｔｓｆｉｅｌｄ和Ｓｍ ｙｔｈ 在［１１］中给出的一个结论σ（Ｋｒ,ｓ）＝ ［（３ｒ＋ ｓ－ ２）／２］是错误的。     

无爪图的f－因子

若图Ｇ不含有导出子图同构于Ｋ＿（１，３），则Ｇ称为无爪图．本文给出了一个无爪图有一个ｆ一因子的充分条件．     

图的广义字典序积的强不可缩回性

通过对图的广义字典序积的强不可缩回性的讨论 ,得到了如下结果 :若对每个x∈V(X) ,图Yx 是非平凡的连通图 ,则X[Yx x∈V(X) ]是强不可缩回的充要条件是每个Yx 都是强不可缩回的 ;若对每个x∈V(X) ,图Yx 有两个连通分支 ,其中恰有一个分支是孤立点 ,则X[Yx x∈V(X) ]是强不可缩回的充要条件是每个Yx 及X都是强不可缩回的 .     

图的自同态半群──I．E—S不可收缩图

本文考虑了图及其自同态半群，给出了Ｅ—Ｓ不可收缩图的结构刻划。     

图的强染色

研究了简单图G（V，E）的强色数Xs(G）的上界与极图及Xs(G)与全色数XT（G）的关系;得到了一些特殊图的强色数Xs(G).     

完全图强乘积的强半径和强直径

首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.     

强乘积图的连通度

用k1＞0和δi表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界κ(G1(□×)G2)≥min{κ1(1+δ2),k2(1+δ1)}.     

图的点强全染色

图G(V,E)的正常k—全染色f叫做G(V,E)的k—点强全染色,当且仅当对任意的w∈V(G),N[w]中元素染不同颜色,其中N[w]={x|wx∈E(G)}∪{w}.并称XvTs(G)=min{k|存在G的k—点强全染色}为图G(V,E)的点强全色数.本文研究了K4-minor free图和外平面图的点强全色数.     

Halin图的一个点强全染色法

针对Halin图的点强全染色问题,提出一个有效的染色法———逐圈着色法,而且方法给出的方案也是最优的,即用最少的颜色完成Halin图的点强全染色.同时还确定了最大顶点度是3的Halin图的点强全色数的上下界,即上界为6,下界为5.     

图的广义字典序积的不可收缩性

研究了图Ｘ与一簇图｛Ｙｘ｜ｘ∈Ｖ（Ｘ）｝的广义字典序积Ｘ「Ｙｘ｜ｘ∈Ｖ（Ｘ）」的自同态幺半群,得到当所有Ｙｘ的团数都相等时,Ｃ２ｎ＋１「Ｙｎ｜ｘ∈Ｖ（Ｃ２ｎ＋１）」是不可收缩的当且仅当每一个Ｙｘ是不可收缩的。     

k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

完全图和完全多部图的Mycielski图的星全染色

讨论了完全二部图、完全图和完全多部图的Mycielski图的星全染色问题,得到了它的星全色数.