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


A local condition for k-contractible edges
Authors:Kiyoshi Ando
Abstract:An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. For a graph G and a vertex x of G, let GNG(x)] be the subgraph induced by the neighborhood of x. We prove that if GNG(x)] has less than ?k2? edges for any vertex x of a k-connected graph G, then G has a k-contractible edge. We also show that the bound ?k2? is sharp.
Keywords:Neighborhood
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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