Article ID Journal Published Year Pages File Type
4657430 Journal of Combinatorial Theory, Series B 2006 20 Pages PDF
Abstract

Kriesell has proved that every noncomplete κ-connected (κ≠7) graph has a κ-contractible edge (i.e., an edge whose contraction yields again a κ-connected graph), if the degree sum of any two vertices with distance at most two is at least . And he guessed that the degree sum condition can be relaxed for only adjacent pairs. In this paper, we verified that is true for κ⩾8.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics