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


Connectivity keeping edges in graphs with large minimum degree
Authors:Shinya Fujita  Ken-ichi Kawarabayashi  
Institution:aDepartment of Mathematics, Gunma National College of Technology, Toribamachi 580, Maebashi, Gunma 371-8530, Japan;bNational Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
Abstract:The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that Gv is still k-connected. In this paper, we consider a generalization of the above result G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63–68]. We prove the following result:Suppose G is a k-connected graph with minimum degree at least left floor3k/2right floor+2. Then G has an edge e such that GV(e) is still k-connected.The bound on the minimum degree is essentially best possible.
Keywords:Connectivity  Minimum degree  Edge deletion
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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