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

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

连通几乎局部连通的强半无爪图

证明了连通几乎局部连通的强半无爪图G,若满足δ（G）≥3,则G是完全圈可扩的,且其中δ（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是拟无爪图。本文证明：连通、几乎局部连通的拟无爪图是完全圈可扩的。     

拟无爪泛圈图的一个充分条件

设G是一个图.若对G中任意距离为2的点对x,y,总存在u ∈ N(x)∩N(y),使得N[u](C)N[x]∪N[y],则称G是拟无爪图.本文给出了拟无爪图是泛圈图的一个充分条件:设G是n阶2-连通无{K4,P5,A}的拟无爪图,G(≠)Cn,则G是泛圈图.     

3—连通正则无爪图的Hamilton圈

证明了每一个3－连通k-正则无爪图G，当G的点数n≤5k-5时，G包含一个Hamilton圈。     

3-连通无爪图的度和与泛圈性

若图G中不含同构于k1,3的导出子图,则称G为无爪图.笔者讨论了3-连通爪图中三个顶点的度和与泛圈性之间的关系,给出了图是泛圈的一个充分条件,得到了如下结果:设图G是n阶3-连通无爪图,如果σ3(G)≥n+1,则G是泛圈的.     

调和平衡图直径与顶点数的关系

如果非平凡连通图G中任意的顶点v都对应G中唯一的顶点,使d(v,)=diam(G),则称G为平衡图.若平衡图G中由边uv∈B(G)可推出∈B(G),则称G为调和平衡图.本文证明了顶点数为n直径为d(d≥5)的调和平衡图G当G≌C_n时有关系式n≥3d.     

三角连通(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)-图是完全圈可扩的.     

距离无爪图的Hamilton性

距离无爪图类属于无爪图类。所谓距离无爪图是对图中的每一个顶点,其距离为的邻域的独立数均不超过3的图.F.BruceShephed已证明:若G是距离无爪图且G是2─连通的,则G有Hamilton路;若G是距离无爪图且G是3─连通的,则G有Hamilton圈.本文在此基础上,定义了一种新的禁用子图──网全爪,首先证明了2-连通的、无网的距离无爪图有Hamilton圈.又证明了2-连通的有网、无网全爪的距离无爪图有Hamilton圈.     

循环图C_(2n)(1,3)的2-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图,称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(│V(G)│-2)/2)的偶匹配M都可以扩充为G的一个完美匹配.刻画了循环图C2(n1,3)的2-偶匹配可扩性,得到结论:对于任意的n(n≥3),C2(n1,3)是2-偶匹配可扩性的.     

拟无爪图的1-因子

拟无爪图是比无爪图更广泛的图类.在拟无爪图中有下面的结论：若G含有偶数个点且是连通的拟无爪图,则G包含1-因子.以上结果扩展了无爪图的相应结果.     

爪心独立图的圈可扩性

设Ｇ是顶点数学不少于３的连通、局部连通图。如果Ｇ的爪心集合是点独立集，并且任意一个爪心的领域所导出的图是强２－控制的，则Ｇ是安全圈可扩的。     

关于图的符号圈(点)控制

引入了图的符号圈(点)控制概念,给出了所有n阶极大平面图G(n≥3)的符号圈(点)控制数γsc(G)的一个下界,即γsc(G)≥(8n - 16 - n△)/△,并且此下界是最好可能的,获得了满足γsc(G)=∣V( G)∣ -2的所有连通图的一个特点.此外,还确定了几类特珠图的符号圈(点)控制数.     

二分图对集的可扩性

设G是一个连通二分图,G=(X,Y;E),本文主要证明了当|X|=|Y|,若δ(G)≥2n+1(1≤n≤|X|2,n∈N),且对G的任两个距离3的顶点u,v有d(u)+d(v)≥|X|+2n时,G是2n-可扩充的     

图的谱半径和泛圈性

设G=(V,E)是一个n阶m条边的简单连通图,μ(G)为图的邻接矩阵的最大特征值。本文利用图的谱条件讨论了图的泛圈性,证明了n(n≥5)阶图G,如果μ(G)n-2,则G是泛圈图除非G=Kn-1+e。     

笛卡尔乘积图的限制边连通性

设G是一个极大限制边连通k-正则图,k≥2．论文证明了：如果│G│〉2k且n≥3,那么笛卡尔乘积图Pn×G是超级限制边连通的,除非G包含子图Kk;如果│G│〉k＋1且n≥3,那么Cn×G是超级限制边连通的,除非n=3且G是圈．     

拟无爪图的性质

讨论了比无爪图更广泛的图——拟无爪图，得到了以下两个结果： (ⅰ)　若图G是拟无爪图，且满足ω(G-S)≤t(G), 则2t(G)=κ(G). (ⅱ) 若图G是拟无爪图，对于任意的控制集D及任意t∈D,至多存在3点u1,u2,u3∈(V-D)满足N(ui)∩D={t}(i=1,2,3), 则γ(G)=i(G)，该结果是最好可能的. 以上结果扩展了无爪图的相应结果.     

随机图G（n，P）中k-团的相变性质

随机图G（n,P）模型是随机图理论中最重要的模型之一。该模型中有两个参数n和P,n表示图中的顶点数,P表示图中的任意两个不同顶点之间独立生成边的概率。证明了随机图G（n,P）中存在k一团的临界值为P=n^-2/k-1;同时证明了随机图G（n,P）中具有k≥3顶点孤立团的连通分量数服从均值λ=e^-x-k3/k!的泊松分布;最后,数值实验分析随机图G（n,P）实例中3-团托：和10一团的相变。数值实验结果表明,实验与理论结果相符。     

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

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