کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650345 | 1342485 | 2008 | 7 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 308, Issue 24, 28 December 2008, Pages 6262–6268