一类Hamilton图

本文证明了：如果Ｇ是２连通无爪图且Ｇ中不含同构于Ｚ３．Ｄ的导出子图．则Ｇ是Ｈａｍｉｌｔｏｎ图（除Ｇ≌Ｇ１．Ｇ≌Ｇ２外）。     

关于k—复盖图的几个条件

设Ｇ是一个图，ｋ为正整数，图Ｇ的一个ｋ－正则支撑子图Ｆ称做图Ｇ的一个ｋ－因子，若图Ｇ的每一条边ｅ都属于Ｇ的一个ｋ－因子，则称Ｇ是一个ｋ－复盖图，本文给出了一个图Ｇ是ｋ的复盖图的几个充分条件。     

一类泛圈图

本文证明了如果 Ｇ 是 ２ 连通无爪图, Ｇ 不是圈,ｎ＝ ｜ Ｖ（ Ｇ）｜≥９, Ｇ 的每个导出子图 Ａ都满足φ（ａ１,ａ２ ）,且 Ｇ 中不含同构于 Ｚ＋２ 的导出子图,则 Ｇ是泛圈图     

关于k－复盖图的几个条件

设Ｇ是一个图，ｋ为正整数．图Ｇ的一个ｋ－正则支撑子图Ｆ称做图Ｇ的一个ｋ－因子．若图Ｇ的每一条边ｅ都属于Ｇ的一个ｋ－因子，则称Ｇ是一个ｋ－复盖图．本文给出了一个图Ｇ是ｋ－复盖图的几个充分条件．     

几类凝聚图的轮廓

设Ｇ是个图，｜Ｖ（Ｇ）＝ｎ｜对Ｇ上的任一个标号ｆ：Ｖ（Ｇ）→｛１，…，ｎ｝记，且当ｊ≠ｉ时，Ｇ中有边以ｆ（－１）（ｊ）及ｆ（－１）（ｉ）为两端点｝）．称Ｐ（Ｇ）＝ｍｉｎ｛Ｐ（ｆ）：ｆ是Ｇ上的标号｝为图Ｇ的轮廓．对以Ｗ表示Ｇ中Ｗ的边界．本文证明：ｉ）若Ｇ是凝聚图，ｆ及ｆ是Ｇ上一对互逆标号，则Ｐ（Ｇ）＝Ｐ（ｆ）的充要条件是ｆ为凝聚标号，且此时若Ｇ，Ｈ均是凝聚图，则存在阶梯标号。使得路、回、完全留之间的下列乘积图也是凝聚图，且其轮廓为     

关于{P2, Ci| i≥3}-覆盖图

设 Ｇ是一个图,若对于 Ｇ的任意一边 Ｇ都有｛Ｐ_２,Ｃｉ｜ｉ－＞３｝－因子含有这条边,则称Ｇ是｛Ｐ_２,Ｃｉ｜ｉ－＞３｝－覆盖图．本文给出连通非二分图Ｇ是｛Ｐ２,Ｃｉ｜ｉ－＞３｝－覆盖图的充要条件为任给Ｓ■Ｖ（Ｇ）,Ｖ（Ｇ）≠Ｓ≠■有ｉ（Ｇ－Ｓ）＿＞｜Ｓ｜－１成立．     

一类泛连通无爪图

本文证明了如果Ｇ是３连通无爪图，且Ｇ的每个导出子图Ａ，Ａ＋都满足（ａ１，ａ２），则Ｇ是泛连通图（除了当ｕ，ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝１时，Ｇ中可能不存在（ｕ，ｖ）－ｋ路外，这里２≤ｋ≤４）．     

关于｛P2,Ci│i≥3｝—覆盖图

设Ｇ是一个图,若对于Ｇ的任意一边Ｇ都有｛Ｐ２,Ｃｉ│ｉ≥３｝－因子含有这条边,则称Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图。本文给出连通非二分图Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图的充要条件为任给Ｓ包含于Ｖ（Ｇ）,Ｖ（Ｇ）≠Ｓ≠ф有ｉ（Ｇ－Ｓ）≤│Ｓ│－１成立。     

（a,b,k）—临界图

设Ｇ是一个图且设ａ，ｂ是非负整数，ａ〈ｂ。如果消去Ｇ的任意ｋ个顶点剩下的图有〔ａ，ｂ〕因子，则称图Ｇ是（ａ，ｂ，ｋ）－临界图。本文给出了一个图是（ａ，ｂ，ｋ）－临界图的一个充分必要条件。讨论了该条件的一些应用，研究了（ａ，ｂ，ｋ）－临界图的性质。     

图的（g，f）－因子和因子分解

设Ｇ是一个图，ｇ，ｆ是定义在图Ｇ的顶点集上的两个整数值函数且图Ｇ的一个（ｇ，ｆ）－因子是Ｇ的一个支撑子图Ｆ使对任意的ｘ∈Ｖ（Ｆ）有本文给出了一个图（ｇ，ｆ）－可因子化的若干充分条件和一个图是（ｇ，ｆ）－消去图的充分必要条件，并研究了这些条件的应用。     

完美路图P3（G）

P_k（G）是指这样的图：G中的所有k路作为P_k（G）的顶点集，两个不同的顶点在Pk（G）中邻接当且仅当它们所对应的两条k路的并为G中的（k＋1）路或k圈，那么，完美图猜想对于路图P_3（G）是成立的．     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

一个伴随等价定理的推广及其简证

记 Gr为任意图 G的 r个拷贝中的对应点 ( r个 )分别与星图 Sr+ 1 的 r个 1度点粘接后得到的图 ,又记 H r为该图 G的相应点与星图 Sr+ 1 的 r度点粘接后得到的图 .如果 G不含三角形 ,则图 ( r- 1) K1 ∪ Gr和图 ( r- 1) G∪ H r伴随等价 ,进而它们的补图色等价     

关于几类图的L(2,1)标号问题

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 ,并证明了上述猜想对以上几类图成立     

两类只含整数根的色多项式

研究了两类只含整数根的色多项式,给出其相应图G为弦图的必要条件,并完全刻画了G的色等价类[G].     

障碍拟阵图

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.     

图G为自构线图的充要条件

首次给出自构线图的定义,并证明:简单图G为自构线图的充要条件是图G为2-正则简单图.