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

拟无爪图的完全圈可扩性

拟无爪图是比无爪图更广泛的图类.证明如下结论:(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-受限爪心独立图是完全圈可扩的。     

连通、局部连通[4,1]-图的圈可扩性

如果图G中任意1个顶点的导出子图中至少含有t条边,则称G为[s,t]-图.笔者证明:如果G是连通、局部连通[4,1]-图,则G是完全圈可扩的或者G属于图类F(Kn11,Kn2,Kn3,K2).     

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

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

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

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是拟无爪图。本文证明：连通、几乎局部连通的拟无爪图是完全圈可扩的。     

几乎局部连通[4,2]-图的圈可扩性

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

图的度和与圈可扩性

讨论了两个点的度和与圈可扩之间的关系,得到了如下结果：设图G的阶n≥3,如果G中任意一对不同的顶点u,v满足d（u）＋d（v）≥n＋1,则G是完全圈可扩的。     

T3-受限图的完全圈可扩性

剖分K1,3的一边所得到的图形叫T3,其中3度顶点x0叫做T3的中心。如果图G中的任意一个与T3同构的子图的三个一度顶点xi（i=1,2,3）之间至少有一条边,则称图G为T3-受限图。如果G满足：（1）G的每个顶点都在三圈上,（2）对G中的任意一个圈C,只要V（C）〈V（G）,就存在G的圈C’,C’满足V（C）包含V（C’）,且｜C＇｜=｜C｜＋1,则称G是完全圈可扩的,C’为C的扩圈。文中证明了：连通、局部连通的T3-受限图是完全圈可扩的。     

5连通无爪图的最长圈

设Ｇ为ｎ阶５连通无爪图，σ６＝ｍｉｎ｛∑ｘ∈Ｉ６ｄ（ｘ）｜Ｉ６为Ｇ的６点独立集｝，则Ｃ（Ｇ）≥ｍｉｎ｛ｎ，σ６－１１｝。     

4连通无爪图的最长圈

设Ｇ为ｎ阶４连通远爪图，δ＝ｍｉｎ（ｄ（ｘ）／ｘ∈Ｖ（Ｇ）），则当ｎ≤６δ－１１时Ｇ为Ｈ图，当ｎ≥６δ－１０时，ｃ（Ｇ）≥５δ－７。     

基于核的有向强连通图计算机随机生成算法

针对图论算法研究和算法测试对随机生成有向强连通图的需求,在深入研究有向强连通图和极小有向强连通图的结构组成的基础上,提出了有向强连通图核的概念。参考有向连通图的随机生成算法,给出了一种有向强连通图的随机生成算法,并对该算法进行了测试。对具有上千个节点及上万条弧的强连通图的随机生成,采用该算法时间都在1 s以内,生成的结果能很好地应用于图论研究,以作为图论算法的随机测试用例。     

有关连通图的连通包数的一些结果

通过图的连通包集和连通包数的定义,确定了测地数、包数和连通包数三者之间的大小关系,并通过一些特殊图(完全二部图、分裂图)构造了连通包数为3的3类图.     

6长圈带2条悬边的8阶连通图的图设计

构造了所需的带洞图设计, 再结合一些小阶数的图设计的存在性, 得到了关于图Gi (i=1,2,3,4)的图设计(v, Gi ,1)-GD的存在谱, 其中图Gi (i=1,2,3,4)是给6长圈增加2条悬挂边所得的8阶连通图, 且G1, G2, G3, G4互不同构.     

图的连通控制的增强数

给出了一些图类确切的连通控制的增强数,并给出图的连通控制增强数的一些紧的界,进而推广了Hedetniemi和Laskar的一个结果.     

三类连通图的伴随唯一性

在寻找色唯一图中,使用图的伴随多项式而不使用色多项式可以得到某些结果·表示n点n+2边连通图中伴随多项式的第三个系数达到其最大值且第四个系数达到其最小值的三类图组成的图族,本文给出这三类图伴随唯一,从而它们的补图色唯一的充分条件·