首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Contractible edges in some k-connected graphs
Authors:Yingqiu Yang  Liang Sun
Institution:1. School of Mathematics, Beijing Institute of Technology, Beijing, 100081, P.R. China
Abstract:An edge e of a k-connected graph G is said to be k-contractible (or simply contractible) if the graph obtained from G by contracting e (i.e., deleting e and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still k-connected. In 2002, Kawarabayashi proved that for any odd integer k ? 5, if G is a k-connected graph and G contains no subgraph D = K 1 + (K 2K 1,2), then G has a k-contractible edge. In this paper, by generalizing this result, we prove that for any integer t ? 3 and any odd integer k ? 2t + 1, if a k-connected graph G contains neither K 1 + (K 2K 1,t ), nor K 1 + (2K 2K 1,2), then G has a k-contractible edge.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号