积图的独立数和上无赘数

证明任意两个图G和H的积图G×H的独立数不小于这两个图的独立数之积,即β(G×H)≥β(G)×β(H);任意两个图G和H的积图G×H的上无赘数不小于这两个图的上无赘数之积,即IR(G×H)≥IR(G)×IR(H).     

一类关于上无赘数的不等式的极图特征

1989年E.J.Cockayne和C.M.Mynhardt得到了一个图图G的上无赘数IR(G)和它的补图G的上无赘数IR(G)之和的一个上界,即IR(G) IR()≤n 1(其中n是G的阶数),而且以Kn为例说明该不等式是可达的.刻画了这个不等式的极图特征及几个相关不等式的极图特征.     

二分图中相互独立的圈

证明了下面的结论：设k≥1是一个整数，G＝（V1,V2；E）是一个二分图，满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1，y∈V2，都有d(x) d(y)≥2k 2，并且δ（G）≥2，则G包含k个相互独立的图。     

关于无爪图最大团数的一个估计

设图G＝（V，E）是一个简单连通图，称所有同边e关联的边集为e的边邻集，记为Г(e)，并称|Г(e)|为e的边度，记为d(e)。在此基础上给出了有关线图的一个充分必要条件和关于无爪图最大团的一个估计。     

饱和二部图

没有完美匹配的二部图G,若给它任意增加一条新的边,结果得到的二部图有完美匹配,则称图G是饱和的.设X包含于V（G）,Γ（X）表示V（G）中与X中至少一个顶点相邻的所有顶点组成的集合.本文证明了一个二部图G=（U,W）是饱和的当且仅当（a）存在唯一X包含于U,使得X〉Γ（X）,X-1〉Γ（X）且G的导出子图G[X∪Γ（X）]是完全二部图;（b）G的导出子图G[（U-X）∪（W-Γ（X））]是完全二部图,且满足U-X＋1=W-Γ（X）;（c）U-X中每个顶点与W中的每个顶点都相邻,且X∪（W-Γ（X））是图G的一个独立集.     

平面连通图为哈密顿图的一个充要条件

本文利用对偶的概念，给出了平面连通图为哈密顿图的一个充要条件。 定理 平面连通图G（V≥3）为哈密顿图的充要条件是存在G的对偶图G＊＝（V＊，X＊）满足： （１） Ｖ＊ ＝Ｖ１＊：Ｖ２８，Ｖ１＊∩Ｖ２＊＝，Ｖ１＊≠，V２＊≠ （２）Ｖ１＊和Ｖ２＊的诱导子图＜Ｖ１＊＞和（Ｖ２＊）均是树。     

关于Cayley图因子的一个注记

Ｃａｙ（Ｓ：Ｇ）表示生成集为Ｓ的群Ｇ上的Ｃａｙｌｅｙ图。本文证明了如下结果：定理ｌ若Ｈ＝Ｃａｙ（Ｓ１：＜Ｓ１＞），则Ｃａｙ（Ｓ：Ｇ）有Ｈ－因子。定理２设Ｓ＝Ｓ１∪Ｓ２∪…∪Ｓｋ，ｓｉ∩Ｓｊ＝φ（ｉ≠ｊ），Γｉ＝Ｃａｙ（Ｓｉ：＜Ｓｉ＞），则Ｃａｙ（Ｓ：Ｇ）是｛Γ１，Γ２，…，Γｋ｝──可分的。     

系列平行图的边色数

Vizing(1964年）和Gupta（1966年）各自独立地证明了边着色中的重要定理：对任何简单图G,表X′（G）＝△或X′（G）△＋1。但确定一个图G的边色数仍是一个尚未解决的问题。本文利用系列平行图的结构性质，确定了它的边色数。     

连通、几乎局部连通拟无爪图是完全圈可扩的

G是一个图，B（G）表示G中所有局部不连通的点构成的集合。如果B（G）是独立集，并且对任意v∈B(G),Eu∈V(G),使G[N(v)∪{u}]连通，则称G是几乎局部连通的。如果G中所有爪心构成的集合D（G）是独立集，并且对任意v∈D(G),G[N(v)]是强2－控制的，则称G是拟无爪图。本文证明：连通、几乎局部连通的拟无爪图是完全圈可扩的。     

S_n和A_n的中心图

设G是一个群,ΓZ（G）是群G的中心图.ΓZ（G）的定义为顶点集是群G的元素,对任意G中的两个不同的元素a,b,若ab∈Z（G）,则a,b相连,其中Z（G）为G的中心.该文主要研究了n元对称群Sn和n元交错群An的中心图.     

关于图是可迹或1—哈密尔顿的两个充分条件

设G是一个图，G的独立集Y称为本质集，如果存在[y1,y2}属于Y，使得dist（y1,y2）＝2。利用插点方法，给出了关于（k-1）或(k 1)－连通（k≥2）图G是可迹的或1－哈密尔顿的统一证明。     

关于边控制集的一些结论

令G＝（V，E）是一个图，M是边集E（G）的子集，如果有e∈E（G）／M，e至少与M中一条边相连，则称M为图G的边控制集，进一步，若M是匹配，则称M为图G独立边控制集，本文给出关于边控制集的一些结论。（1）设图H，S是两中连勇图，且H,S∈ж，γe(S)=1,M和M′＝｛uv｝分别是图H和S的唯一最小边控制集，其中S是图1中的（G1，G2，G3，G4）四个图之一，对任何点x∈V（S）＝｛u,v｝,y∈V(H)-V(M),令G＝H（y=s)S，则G∈ж，（2）如果连通图G≠K2，G∈ж，γe(G)=k,则存在G的两个连通于图H，S和某两个正整数l,m使H∈ж，S∈ж，且γe(H)=k-l,γe(S)=l,G≌H（yi=xi)S,其中l≤i≤m.     

不含K1＋P3和C4作为导出子图的图的色数

Erodos证明了对于一个图G ,χ（G）-ω（G）可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类 F-free图的色数和团数的关系。得到了如果图G是一个不含K 1＋ P3和C4作为导出子图的图,那么当α（G ）≥3时,χ（G ）＝ω（G ）;当α（G ）＝2时,χ（G ）n ≤2ω（G ）。     

3-边连通图中的超欧拉图

一个含有生成闭迹的图称为超欧拉图。设G是n阶3－边连通图，若对任意G的边数为3的最小边割E都满足G－E遥每一连通分支的阶至少为（n-1）／10，则或者G是超欧拉图，或者G可收缩为G‘＝Petersen图，且G‘的每个顶点在G中的原像是G的一个可折叠子图，其顶点数至少是（n-1）／10。     

1—坚韧Hamilton图的充分条件

设n≥3阶1—坚韧图,若对于G中任意导出爪K(1．3)或变爪K(1．3)＋e上的三点u,v,w,且d（u,v）＝d（u,w）＝2,均满足｜N（u）∩N（v）｜≥-α－1或｜N（u）∩N（w）｜≥α－1,则G是Hamilton图。     

关于3—控制临界图的某些结果

以γ（Ｇ）记图Ｇ的控制数，如果对Ｖ（Ｇ）中任何一对满足条件ｕｖ不包于Ｅ（Ｇ）的顶点ｕ，ｖ，有γ（Ｇ＋ｕｖ）＜γ（Ｇ），则称Ｇ是控制临界的γ（Ｇ）＝ｋ的控制临图图称为是ｋ－控制临界的，得出以下两个结果：１）如果Ｇ是具有ｎ（＞＞２ｋ）个顶点的连通３－控制临界图，则Ｇ中度≤２ｋ的顶点的个数至多为２ｋ，２）每个连通３－控制临界图或者有一个独立３－控制集或者有一个完全３－控制集。     

有限非交换群的交换图的一些性质

设G是一个有限非交换群,ΓG是G的一个交换图,这个交换图ΓG的顶点集为群G的所有元素,ΓG的两个不同顶点x和y是相连的当且仅当xy=yx.该文研究了交换图的一些性质,具体介绍了几个交换图同构的例子.     

图的全-Domination染色

图G的一个全-domination染色是图G的一个正常点染色,使得G的每个顶点v控制除了v以外的至少一个色类,并且每一个色类被G中至少一个顶点控制。图G的全-domination染色所需的最少颜色数称为G的全-domination色数,记为χ_td（G）。本文通过图构造的方法证明了对于任意的图G和任意固定的整数k≥1,决定χ_td（G）=k是否是NP-完全的,并研究了χ_td（G）和χ_td（G^′）之间的关系,这里G^′是G通过某种操作得到的图。     

Hamiltion图的一个充分条件

证明如下结果：G是简单图满足条件：对G中任一对不相邻顶点u、v有max{d(u),d(v)} ｜N(u)∪N(v）｜≥n-1；且对任意T包含V（G），有ω（G\)≤｜T｜，则G是Hamilton图。     

奇数阶6度边传递Cayley图

关于有限群G的Cayley图Γ=Cay(G,S)称为边传递,如果图Γ的全自同构群Aut(Γ)在边集合E(Γ)上作用传递.该文给出了奇数阶6度边传递Cayley图的一个刻画.