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


The number of contractible edges in 3-connected graphs
Authors:Katsuhiro Ota
Affiliation:(1) Department of Information Science, Faculty of Science, University of Tokyo, Hongo, Bunkyo-ku, 113 Tokyo, Japan
Abstract:An edge of a 3-connected graph is calledcontractible if its contraction results in a 3-connected graph. Ando, Enomoto and Saito proved that every 3-connected graph of order at least five has lceil|G|/2rceil or more contractible edges. As another lower bound, we prove that every 3-connected graph, except for six graphs, has at least (2|E(G)| + 12)/7 contractible edges. We also determine the extremal graphs. Almost all of these extremal graphsG have more than lceil|G|/2rceil contractible edges.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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