恰含5条非基本边的极小3连通图  

MINIMALLY 3-CONNECTED GRAPHS WITH EXACTLY FIVE NON-ESSENTIAL EDGES

作　　者：陈仪朝[1] 苏健基[1] 

机构地区：[1]广西师范大学数学与计算机科学学院,广西桂林541004

出　　处：《广西师范大学学报（自然科学版）》2004年第3期29-34,共6页Journal of Guangxi Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目 ( 1 0 1 71 0 2 2 )

摘　　要：简单极小 3连通图 G中的一条不在任何三边形中的边 e收缩之后所得到的图如果仍 3连通 ,则称 e为 G的非基本边 .Oxley与 Wu证明不是轮的简单极小 3连通图至少包含 3条非基本边 ,并且刻画了恰含 3条或 4条非基本边的不是轮的简单极小 3连通图 .现刻画恰含 5条非基本边的不是轮的简单极小 3连通图 ,它们是 1Let G be a simple 3-connected graph.An edge e of G is called deletable if the deletion G-e is 3-connected.A contractible edge e of G is an edge whose contraction yields again a 3-connected graph.If an edge e of G is not in any triangle and is contractible,then call e simple contractible edge of G.Tutte called an edge essential if it is neither deletable nor simple-contractible.Oxley and Wu proved:that if G is a minimally 3-connected graph other than a wheel then G has at least three non-essential edges,and moreover,G has exactly three non-essential edges if and only if G is a split-wheel or a crossed split-wheel,G has exactly four non-essential edges if and only if a three fan or a doubly interlocked wheel.This paper specifies all such minimally 3-connected graphs with exactly 5 non-essential edges.

关 键 词：图论 极小3连通图 可收缩边 非基本边 扇 

分 类 号：O157.5[理学—数学]