5连通图的分裂和可收缩边

引入5连通图中度为5的顶点的分裂,利用分裂和收缩的运算对某类5连通图进行归纳,证明了对于阶至少为7的5连通图G,当G的任一断片的阶不等于2,且对G的任一5度顶点z,G[NG(z)]中含子图(K2∪2K1)+K1,则对G的任意顶点x,下列断言之一成立:1)x关联一条可收缩边;2)在NG(x)中存在一个5度顶点y关联一条可收缩边;3)在NG(x)中存在一个5度顶点y,使得对y作某一个分裂运算所得的图是5连通的.

收缩临界5连通图中5度点的分布

当G是收缩临界5连通图,x∈V(G)且d(x)≥6,x1,x2为与x相邻的5度点时,证明如果x1x2∈E(G),则x与3个5度点相邻.

子式极小的Super-5连通图

如果图G可以经过去边,或者去点,或者收缩子图得到子图H,则称H是G的子式。若G是k-连通图且G中不包含另外一个k-连通图作为子式,则称G是子式极小的k-连通图。M. Krisesell证明了子式极小的hyper-5连通图的顶点数至多是12。本文将这个结论推广到Super-5连通图。

收缩临界5-连通图的平均度(英文)

M.Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10.本文构造了一个反例证明M.Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界.

收缩临界5-连通图最长圈上的5度点

讨论收缩临界5-连通图最长路和最长圈上5度点的分布情况,刻画收缩临界5-连通图的结构.

围长g>7的极大5限制边连通图的充分条件

设G=(V,E)是一个λk-连通图,称图G的λk-割所含边的数目为G的k限制边连通度.定义ξk(G)=min{|[X,Y]|∶|X|=k,G[X]连通,Y=V(G)\X}.拟研究λ5(G)=ξ5(G)的围长条件.

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

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

5-连通的收缩三元组(英文)

证明了任意5-连通图G存在一条路P满足|V(P)|=3使得G-P是3-连通,在k=3的情形推广了W.Mader的结果.

图是λ_5-最优的充分条件

文章给出了图是λ5-最优的邻域交条件.设G是一个λ5-连通图,定义ξ5(G)=min{|[X,]|:X∈V(G),|X|=5,G[X]连通},若λ5(G)=ξ3(G),则称G是λ5-最优的.若对G中任意一对不相邻的顶点u和v,都有|N(u)∩N(v)|≥5且G满足ξ3(G)≤V(G)/2+10,|V(G)|≥31,则G是λ5-最优的.