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

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

最近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.