不含某些子图的k连通图中的k可收缩边  

k-CONTRACTIBLE EDGES IN k-CONNECTED GRAPHS NOT CONTAINING SOME SPECIFIED GRAPHS

作　　者：杨迎球[1,2] 苏建基[3] 

机构地区：[1]北京理工大学理学院数学系,北京100081 [2]安顺学院数学与计算机科学系,安顺561000 [3]广西师范大学数学科学学院,桂林541004

出　　处：《系统科学与数学》2010年第7期922-928,共7页Journal of Systems Science and Mathematical Sciences

摘　　要：最近Ando等证明了在一个k(k≥5是一个整数)连通图G中,如果δ(G)≥k+1,并且G中既不含K_5^-,也不含5K_1+P_3,则G中含有一条k可收缩边.对此进行了推广,证明了在一个k连通图G中,如果δ(G)≥k+1,并且G中既不含K_2+([k-1/2]K_1∪P_3),也不含tK_1+P_3(k,t都是整数,且t≥3),则当k≥4t-7时,G中含有一条k可收缩边.Recently,Ando et al.proved that in a k-（k≥5 is an integer） connected graph G,ifδ（G）≥k ＋ 1,and G contains neither K_5^-,nor 5K_1 ＋ P_3,then G has a k contractible edge.In this paper,the result is generalized,and it is proved that in a k- conneted graph G, ifδ（G）≥k ＋ 1,and G contains neither K_2 ＋（[（k-1）/2]K_1∪P_3）,nor tK_1 ＋ P_3（both k and t are integers,and t≥3） and if k≥4t- 7,then G has a fc contractible edge.

关 键 词：断片 可收缩边 k连通图 

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