3连通图生成树上的可去边  

Removable edges in a spanning tree of a 3-connected graph

作　　者：吴吉昌[1] 李学良[2] 

机构地区：[1]西北工业大学计算机科学与工程系,陕西西安710072 [2]南开大学组合数学研究中心,天津300071

出　　处：《兰州大学学报（自然科学版）》2003年第6期8-11,共4页Journal of Lanzhou University(Natural Sciences)

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

摘　　要：设 G是 3连通图 ,e是 G中的一条边 .若 G-e是 3连通图的一个剖分 ,则称 e是 3连通图 G的可去边 .否则 ,称 e是 G的不可去边 .本文给出某些An edge of a 3-connected graph G is said to be removable if G-e is a subdivision of a 3-connected graph.In this paper,we obtain the following two results:if G is a 3-connected graph of minimal degree at least four,then every spanning tree of G contains at least two removable edges of G.If G is a 3-connected graph of girth at least four,then every spanning tree of G contains at least two removable edges of G.

关 键 词：3连通图 生成树 可去边 

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