Article ID Journal Published Year Pages File Type
4649075 Discrete Mathematics 2007 17 Pages PDF
Abstract

It is shown that an essentially 6-connected graph G on at least 13 vertices can be contracted to a 5-connected graph H   such that 0<|V(G)|-|V(H)|<50<|V(G)|-|V(H)|<5. The bounds 13 and 5 are sharp, and no such result holds for higher connectivity.

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