A local structure theorem on 5‐connected graphs |
| |
Authors: | Kiyoshi Ando |
| |
Affiliation: | Department of Information and Communication Engineering, the University of Electro‐Communications, 1‐5‐1 Chofugaoka, Chofu‐City, Tokyo 182‐8585, Japan |
| |
Abstract: | An edge of a 5‐connected graph is said to be contractible if the contraction of the edge results in a 5‐connected graph. Let x be a vertex of a 5‐connected graph. We prove that if there are no contractible edges whose distance from x is two or less, then either there are two triangles with x in common each of which has a distinct degree five vertex other than x, or there is a specified structure called a K4?‐configuration with center x. As a corollary, we show that if a 5‐connected graph on n vertices has no contractible edges, then it has 2n/5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009 |
| |
Keywords: | 5‐connected graph contractible edge |
|
|