Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650812 | Discrete Mathematics | 2008 | 6 Pages |
Abstract
An edge of a kk-connected graph is said to be kk-contractible if the contraction of the edge results in a kk-connected graph. In this paper, we prove that a (K1+C4)(K1+C4)-free minimally k-connected graph has a k-contractible edge, if incident to each vertex of degree k, there is an edge which is not contained in a triangle. This implies two previous results, one due to Thomassen and the other due to Kawarabayashi.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kiyoshi Ando, Atsushi Kaneko, Ken-ichi Kawarabayashi,