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


The number of vertices of degree 5 in a contraction-critically 5-connected graph
Authors:Kiyoshi Ando  Takashi Iwase
Institution:aDepartment of Informatics, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu City, Tokyo, 182-8585, Japan;bDepartment of Measurement System Development, Anritsu Engineering Co., Ltd., 5-1-1 On-na, Atsugi-City, Kanagawa 243-0032, Japan
Abstract:An edge of a 5-connected graph is said to be 5-contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no 5-contractible edge is said to be contraction-critically 5-connected. Let V(G) and V5(G) denote the vertex set of a graph G and the set of degree 5 vertices of G, respectively. We prove that each contraction-critically 5-connected graph G has at least |V(G)|/2 vertices of degree 5. We also show that there is a sequence of contraction-critically 5-connected graphs {Gi} such that limi|V5(Gi)|/|V(Gi)|=1/2.
Keywords:5-connected graph  Contraction-critically 5-connected  Degree 5 vertex
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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