Article ID Journal Published Year Pages File Type
4650345 Discrete Mathematics 2008 7 Pages PDF
Abstract

An edge of a kk-connected graph is said to be kk-contractible if its contraction yields a kk-connected graph. A non-complete kk-connected graph possessing no kk-contractible edges is called contraction-critical kk-connected. Let GG be a contraction-critical 7-connected graph with nn vertices, and V7V7 the set of vertices of degree 7 in GG. In this paper, we prove that |V7|≥n22, which improves the result proved by Ando, Kaneko and Kawarabayashi. In the meantime, we obtain that for any vertex x⁄∈V7x⁄∈V7 in a contraction-critical 7-connected graph there is a vertex y∈V7y∈V7 such that the distance between xx and yy is at most 2, and thus extends a result of Su and Yuan. We present a family of contraction-critical 7-connected graphs GG in which V7V7 is independent.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,