Premium
A local structure theorem on 5‐connected graphs
Author(s) -
Ando Kiyoshi
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20350
Subject(s) - combinatorics , mathematics , contractible space , corollary , vertex (graph theory) , discrete mathematics , edge contraction , connectivity , graph , line graph , graph power
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 K 4 − ‐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 2 n /5 vertices of degree 5. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 99–129, 2009