连通、弱局部连通、K1,P-约束图的完全圈可扩性

给出了弱局部连通的定义，证明了顶点数不少于3的连通图、弱局部连通图、Kl,p-约束图是完全圈可扩的，改进了朱永津、王江鲁(1998)文中关于蜀Kl，p-约束图的完全圈可扩性的相应结果。     

(s,k)-连通图

图G为（s,k）-连通图,如果G中任意s个顶点的导出子图是k-连通的。证明了：如果s-k≤｜G｜-1/2,则（s,k）-连通图G是完全圈可扩的。由此推出,若图G的连通度κ（G）≥｜G｜＋1/2,则G是完全圈可扩的。     

[4，2]-图的圈可扩性

如果图G的任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图。证明:顶点数≥3的连通、局部连通[4,2]-图是完全圈可扩的或者同构于K2∨K3。     

连通、几乎局部连通、强K1,p-约束图的完全圈可扩

借助于新的连通性——几乎局部连通的定义，证明了连通、几乎局部连通、强K1．p-约束图的完全圈可扩。这一结果涵盖了拟无爪图上的相应结果。     

[4,1]-图的圈可扩性

如果图G的任意s个顶点的导出子图中至少含有t条边,则称图G为[s,t]-图。本文证明了连通、局部2-连通[4,1]-图是完全圈可扩的。     

5-连通图的可收缩边的分布

图的可收缩边问题对于研究图的结构和证明图的某些性质有着重要作用。本文给出了5-连通图中某些最长圈可收缩边的分布情况,用树型结构理论进行分类讨论,得到如下结论:不含2-断片的5-连通图的最长圈上至少有三条可收缩边。     

拟无爪图的完全圈可扩性

拟无爪图是比无爪图更广泛的图类.证明如下结论:(i)顶点数 n ≥ 3 的连通、局部连通的拟无爪图是完全圈可扩的;(ii)若 G2是顶点数 n ≥ 3 的连通的拟无爪图,则G2是完全圈可扩的.这些结论推广了无爪图及拟无爪图中的相应结论.     

三角连通[4,2]-图的完全圈可扩性

如果G的任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.本文证明了:若G是无孤立点的三角连通[4,2]-图,则G或者是完全圈可扩的或者同构于F.其中图F有与图■∨K2同构的导出子图.     

连通、几乎局部连通爪心独心K1．4-受限图是完全圈可扩的

设G是一个图,B={v∈V(G)|不连通},如果B是独立集,并且v∈B,u∈V(G),使连通,则称G是几乎局部连通图。证明了连通、几乎局部连通K1,4-受限爪心独立图是完全圈可扩的。     

三角连通(K1,4;2)-图的完全圈可扩性

对于任意一对边e1,e2∈E(G),在G中存在一系列3-圈C1,C2…,Cl使得e1∈C1,e2∈Cl且E(Ci)∩E(Ci 1)≠Φ(1≤i≤l-1),则称图G为三角连通的.本文证明如下结论:顶点数不小于3,无孤立点,爪心独立的三角连通(K1,4;2)-图是完全圈可扩的.     

对2连通n阶图某些结果的改进

研究 NC≥ n-δ条件下 Cnm 点泛圈图的性质 ,得到 2连通 n(n≥ 6 )阶图 G.若 N C≥ n-δ,则 G是 Cn5 点泛圈图或 Kn/ 2 ,n/ 2 .改进了 Faudree等人的一些结果     

三个5-阶图与圈Cn联图的交叉数Cn

联图G∨H表示将G中每个点与H中的每个点连边得到的图．在Klesc M给出所有3阶图和4阶图与圈Cn联图的交叉数的基础上,利用反证法和排除法确定了G1,G2,G3三个5-阶图与圈Cn联图的交叉数,他们的交叉数分别是cr（G1∨C2）=Z（5,n）＋2[n/2]＋2,cr（G2∨Cn）=Z（5,n）＋2[n/2]＋2,cr（G3∨Cn）=Z（5,n）＋2[n/2]＋3.     

边染色临界图主顶点数的一个结果

如果一个连通的第二类图G去掉任意一条边后其边色数都比图G小,则称它是一个临界图.最大顶点度为△的临界图称作△-临界图.1968年,Vizing猜想任意n阶△-临界图G边数m的下界为（nΔ-n＋3）/2.Fiorini不等式和差值转移法被广泛用于研究此猜想.笔者利用Vizing邻接引理和临界图的结构性质给出了Δ-临界图在△≥6且（Δ-1）度顶点至多邻接一个四度顶点时Fiorini不等式的一个新的下界.     

圈的2顶点扩张图的最大强直径的一个下界

给定一个无向图G,将G的每条边{x,y}用弧xy或yx替代后得到的有向图称为G的定向图．若连通图G在定向后是强连通的,则称该定向为G的强定向．使得G的所有定向图中强直径最大的定向称为G的最大强直径定向．文章给出了矿圈（其中n≥3）的2顶点扩张图的最大强直径的一个下界．     

G10×Sn的交叉数

本文证明了五阶图G10与星Sn的笛卡尔积交叉数,填补了Marian Klesc所给出的五阶图与星图的笛卡尔积交叉数表格中的又一个空白.     

非连通图Gn-1k∪i=0C3i（2n＋1）的优美性

证明了当自然数n≥2时,非连通图Gn-1k∪i=0 C3i（2n＋1）是优美图,其中C3i（2n＋1）是有3i（2n＋1）个顶点的圈（i为自然数）,Gn-1是任意一个有n-1条边的优美图.     

6-连通图最长圈上的可收缩边

 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图一些性质的有力工具。设G是一个6-连通图,e∈E（G）,若收缩e后得到的图仍是6-连通的,则称e是G的可收缩边。采用树型结构理论进行分类讨论,得到如下结论：① 如果P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,xi xi+1是一条不可收缩边,且S={xi,xi+1,u1,u2,u3,u4}是其对应的6-点割,则G-S的每一个断片至少包含P上的一个点;② 设P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,且G的任意断片的阶都大于2。如果P上任意顶点xi都满足条件d（xi）≥7或者若d（xi）=6则[V（P）]中无3-圈包含它,那么P上至少包含一条可收缩边。在上述结论的基础上,进一步研究了任意断片阶都大于2的6-连通图中最长圈上的可收缩边的分布情况,得到如下新结果：任意断片阶都大于2的6-连通图最长圈上至少有两条可收缩边。     

几乎局部连通［4,2］-图的圈可扩性

如果图G的任意s个顶点的导出子图中至少含有t条边,则称图G为［s,t］-图。本文证明:连通、几乎局部连通［4,2］-图中任意一个满足5≤｜C｜≤｜G｜的圈是可扩的。     

一个五点图和路的联图的交叉数

计算了一个具体图类Hn的交叉数,然后研究了一个五点图G和Pn路的联图G∨Pn,并用归纳假设法证明了这个五点图和路的联图的交叉数Cr(G∨Pn),即当n≥2时,Cr(G∨Pn)=4 2n n 2-1+n2+1.     

蛛形图的D（3）-点可区别的全染色

利用穷举法和组合分析法讨论了蛛形图的D（3）-点可区别的全染色，得到了蛛形图的D（3）-点可区别的全色数．