4-连通图中圈上的可去边和可收缩边

给出某些4 连通图中圈上的可收缩边和可去边的分布情况,得到如下结果:最小度至少为4或围长至少为5的4 连通图,其任一圈上至少有两条可去边;对4 连通图中的某些最长圈上至少有两条可收缩边.

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

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

强4-连通图的可收缩边

该文主要研究强4—连通图G上的可去边的数目,证明了强4-连通图G的任何一个生成树T上至少有3条可收缩边.进一步证明了除了一个特殊图外强4-连通的任意最长圈C上至少有5条可收缩边.有例子表明该文的结果是最好可能的.

收缩临界3-正则内部4-连通图的结构刻画

若图G的每个3-点割T都不包含边且能分离出一个3度点,则称G是内部4-连通的.设G是内部4-连通图,e是G的一条边,若G/e仍是内部4-连通的,则称e是可收缩的.不含可收缩边的内部4-连通图G称为收缩临界内部4-连通图.该文证明了图G是收缩临界3-正则内部4-连通图当且仅当G是柱面体图或莫比乌斯柱面体图.

4-强连通竞赛图中外弧泛圈点的研究

外弧泛圈点问题是图论研究中一个比较热门的问题,文章在某些限制条件下研究了4-强连通竞赛图的外弧泛圈点问题。文中使用路收缩等方法证明并给出了4-强连通竞赛图中存在3个外弧泛圈点的一个充分条件,而且给出了一些相关的结论。