Some structural properties of minimally contraction-critically 5-connected graphs |
| |
Authors: | Kiyoshi Ando Qin Chengfu |
| |
Institution: | aDepartment of Information and Communication Engineering, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu City, Tokyo, 182-8585, Japan;bDepartment of Mathematics, XiaMen University, 310065 XiaMen, PR China |
| |
Abstract: | An edge of a k-connected graph is said to be k-removable (resp. k-contractible) if the removal (resp. the contraction ) of the edge results in a k-connected graph. A k-connected graph with neither k-removable edge nor k-contractible edge is said to be minimally contraction-critically k-connected. We show that around an edge whose both end vertices have degree greater than 5 of a minimally contraction-critically 5-connected graph, there exists one of two specified configurations. Using this fact, we prove that each minimally contraction-critically 5-connected graph on n vertices has at least vertices of degree 5. |
| |
Keywords: | 5-connected graph Contraction-critically 5-connected Degree 5 vertex |
本文献已被 ScienceDirect 等数据库收录! |
|