6连通图中的可收缩边(英文)  

Contractible Edges in 6 Connected Graphs

作　　者：袁旭东[1] 苏健基[1] 

机构地区：[1]广西师范大学数学系,桂林广西541004

出　　处：《数学进展》2004年第4期441-446,共6页Advances in Mathematics（China）

基　　金：The work partially supported by NNSF of China(No.10171022)

摘　　要：Kriesell(2001年)猜想:如果k连通图中任意两个相邻顶点的度的和至少是25k/4-1,则图中有k-可收缩边.本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点,由此推出该猜想对k=6成立.Kriesell conjectured that every K, connected graph has a k-contractible edge if the degree sum of any two adjacent vertices is at least 2 5k/4- 1. In this note, we proved that every contraction-critical 6 connected graph contains two adjacent vertices of degree 6, so this conjecture is true for K = 6.

关 键 词：连通图 收缩临界连通 可收缩边 分离集 断片 

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