一类极大临界h连通图的结构

引入图的粘合的概念,进一步研究最小度等于3h/2-1的极大临界h连通图均性质,给出一个图是这类图的一个充要条件,由此给出这类图的一种新的构造方法,更易操作．     

一类极大临界h连通图的性质

设G是h连通图，图G的顶点υ称为临办点，G－υ不再h连通，如果G的每个顶点都是临界的，则称G为临界h边连通图。对于G中任意两个相邻的项点x与y，G＋xy不再临界h连通，则称G为极大临界h连通图。引入图的粘合的概念，讨论了δ（G）＝3h／2－1的极大临界h连通图的性质，得到了这类图有关原子，最小点割和分支的重要性质，这有利于进一步研究这类图的结构。     

一类极大临界4连通图的结构

引入图的粘合的概念,讨论了极大临界4连通图的性质,给出了一个图是这类图的一个充分必要条件,由此给出该类图的一种新的构造方法.     

泛圈图的一个充分条件

在文[1]中给出定理,设G是一个n-阶2-连通图且δ（G）≥t,若对于G的任意两个不相邻的点u和v,均有｜N（u）∪N（v）｜≥n-t成立,则G是一个泛圈图或G≌Kn/2,n/2.本文的目的在于将此定理的条件减弱,只对图中距离为2的点进行讨论,得出了泛圈图的一个充分条件.文中主要用数学归纳法对定理进行证明,先在引理中给出了几种特殊情况的证明,接着在定理的证明中讨论了一般情形.     

2-连通图过指定边的长圈

对2-连通非完全图G，令μ(G)=min{max{dG(v)}|dG(u,v)=2}．一个著名的范定理;每一个2-连通非完全图G包含长至少为min{|V(G)|，2μ(G)}的圈．在这篇论文中我们证明了：若G是2-连通无三角形图，则通过G的任一边存在长至少为min{|V(G)|，2μ(G)}的圈．     

关于哈密顿图的一点注记

如果图G含有一个过G中每个顶点恰好一次的圈,则称G是一个哈密顿图。对于含有两个不相邻顶点a和b的图G,本文给出了一些条件,如果G满足这些条件,且G ab是哈密顿图,则G也是哈密顿图。     

具有二分划(A_1;A_2)的2-连通偶图为(A_1;A_2)Hamilton连通的一个充分条件

给出具有二分划(A1,A2)的n阶2连通偶图G(A1,A2)为(A1,A2)Hamilton连通的定义,其中|A1|=|A2|·采用反证法,将图G分为若干情形,利用图G是2连通的偶图,及|A1|=|A2|,证明了,若n≤2δ+2δ-2时,则G是(A1,A2)Hamilton连通图,其中δ=min{d(x)|x∈V(G)},δ=min{max(d(x),d(y))|d(x,y)=2,x,y∈V(G)}·     

具有二分划(A1,A2)的2－连通偶图为(A1,A2)Hamilton连通的一个充分条件

给出具有二分划 (A1,A2 )的n阶 2连通偶图G(A1,A2 )为 (A1,A2 )Hamilton连通的定义 ,其中 |A1|=|A2 |·采用反证法 ,将图G分为若干情形 ,利用图G是 2连通的偶图 ,及 |A1|=|A2 |,证明了 ,若n≤ 2δ +2δ - 2时 ,则G是 (A1,A2 )Hamilton连通图 ,其中δ =min{d(x) |x∈V(G) } ,δ =min{max(d(x) ,d(y) ) |d(x ,y) =2 ,x ,y∈V(G) }·     

关于图的可达划分数

本文给出了E.J.Cockayne和S.T.Hedetniemi的下列猜想的一个新证明:当图G的团图为2-分图时,G的最小团的阶数不大于G的可达划分数;讨论了图的可达划分数与连通度的关系。     

关于判定超欧拉图的收缩法

P.A.Catlin提出一个问题：设H是图G的一个连通子图，如果G关于H的收缩图G/H有一个欧拉生成子图，那么在什么条件下G也有一个欧拉生成子图？研究了这一问题，讨论了Catlin提出的用收缩法判定超欧拉图的两个定理，给出了一些实用的超欧拉图的判别方法。     

临界极小2连通图的构造

连通极值图类的构造,是图论研究中的一个重要课题,本文对唯一剩下没有被构造出的2(边)连通极值图类——临界极小2连通图类进行了研究,得出了一个特征定理,构造出这个图类。同时,本文研究了临界与极小之间的关系,在构造出临界极小2连通图类的基础上,用新的方法构造出临界2连通图类和极小2连通图类。     

非基本最短欧几里德2-连通Steiner网络的几个性质

欧几里德2-连通Steiner网络问题是组合优化中的著名问题,在水、电供应网络等的设计中有非常广泛的应用.以块图为工具,证明了非基本最短欧几里德2-连通Steiner网络的一些结构性质.     

2连通的k正则偶图的周长

本文证明2连通的k正则偶图G的周长至少为min{|V(G)|,4k+2},且是最好可能的。     

近似2-连通k-支配容错虚拟主干网

由于无线网络存在节点失效、链路断裂等特性,虚拟主干网需要具备一定的容错性。利用2-连通k-支配集作为容错虚拟主干网的模型。通过分析单位圆盘图中极大独立集的性质和连通图的块-割点树结构,首次设计出在无线自组织网络中构造2-连通k-支配虚拟主干网的近似算法。从理论上分析了该算法的时间复杂度,并证明了该算法的近似比为常数。     

两类2连通(n,n+4)图的色唯一性

2连通的(n,n 4)图是有n个顶点n 4条边的连通图,利用图的色多项式理论研究了两类2连通的(n,n 4)图的色性,由此部分或完全解决了图G5和图G12的色唯一性问题.     

4连通图中生成树上的可去边

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具.利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况,得到了最小度至少为5或围长至少为4的4连通图中在其生成树上存在至少两条可去边;同时也得到了最小度至少为5的4连通图中在其生成树外存在至少两条可去边.     

无可收缩边的4—连通图的特征

本文证明了无可收缩边的4-连通图是两类特殊的4-正则图.这一结果推广了M.Fontet在[7]和[8]中的结论.     

最少边数的n阶3-点连通简单图及其构造

从图的度数列入手,采用一种特殊的构造方法,不仅得到了3-点连通简单图的最少边数c(G)的值,还得到了图的边数最少时的连通简单图.     

收缩临界5-连通图的局部结构(英文)

证明了收缩临界5-连通图G中任意一点x,当d(x)≥6时就有G[N(x)∩V5(G)]不是一个完全图,从而推广了李婷婷的结果(李婷婷,收缩临界5连通图中5度点的分布,广西科学,2009,16(1):13-16).