分数Hamilton圈与分数树形图

定义有向图的分数有向Hamilton圈和分数支撑树形图，讨论分数Hamilton圈、分数旅行售货员问题和分数支撑树形图基于线性规划的等价定义及多项式时间算法。     

一个关于2─连通图周长的次条件

设Ｇ为ｎ阶２－连通图，顶点ｖ１，ｖ２，…，ｖｎ满足ｄ１≤ｄ２≤…≤ｄｎ，其中ｄｉ＝ｄ（ｖｉ），ｉ＝１，２，…，ｎ。给出ｃ（Ｇ）≥ｍｉｎ｛ｎ，ｍ｝的如下条件：     

极大局部边连通有向图的度条件

对有向图D=(V(D),E(D)),顶点u和v的局部边连通度λ(u,v)=min {X:X∈E(D),D-X中不存在从u到v的路}.若对D中任意两个顶点u和v,λ(u,v)=nin{d+(u),d-(v)},称D为极大局部边连通的.笔者得到了有向图是极大局部边连通的两个度条件.推广了别人的三个结果.     

极大局部边连通和超级局部边连通二部有向图的邻域条件

本文主要证明了对于n阶二部有向图D，当最小度δ≥3,对任意同部顶点x，y,有min{|N⁺(x)∪N⁺(y)|，|N^-(x)∪N^-(y)|}≥(n+3)/4]时,D为极大局部边连通的；当最小度δ≥4,对任意同部顶点x，y,有min{|N⁺(x)∪N⁺(y)|,|N^-(x)∪N^-(y)|}>(n/4)+1时,D为超级局部边连通的。我们证明了条件的最好可能性及结果与原有结果的独立性。     

赋权图中最重的最长v-路与赋权周长

对2－连通非Hamilton赋权图G,本文证明：若P（u,v)是G中最重的最长路，则G的赋权周长C^w(G)≥d^w(u) d^w(v)，假设G满足文中描述的额外条件C1，C2，则max｛d^w(x),d^w(y)|d(x,y)=2｝≥m/2时，对每个顶点v,G含量最重长v-路P（u,v)使d^w(u)≥m/2，而d^w(x) d^w(y) d^w(z)≥m（当d(x,y,z)=2)时，c^w(G)≥2m/3.改进了非赋权图的周长及赋权图的赋权周长的若干已有结果。     

模和图的饱和点数

{1，2，…，m-1}的非空子集S关于模m的模和图是图（S，E），其中ω∈E当且仅当U＋V（mod m）∈S．文章证明了模和图至多有一个饱和点，即与其它点都相邻的点．     

2-连通无爪图的泛连通性

一个图称作无爪图,如果它不含同构于K_(1,3)的导出子图。很重要的一类图——线图就是无爪的。目前已有的结果表明:相对于一般图而言,无爪图具有较好的性质。 关于无爪图的Hamilton性质,近年来     

有向图和二部有向图的局部边连通性

笔者首先利用顶点的度和给出了有向图是超级局部边连通的一个最好可能的充分条件,然后提出了二部有向图为极大局部边连通和超级局部边连通的度序列条件.这些结果在网络可靠性分析中有一定应用.     

正则图m-限制边连通度的存在性

图G的m-限制边割是删除它以后G不连通,且留下的每个分支的阶至少为m的边子集;m-限制边割的最小基数称为m-限制边连通度。设G是连通（k-2）-正则图,阶至少为2k（k≥5）。证明了G的k-限制边连通度存在当且仅当G不属于一种特殊图类G^＊ k-2.