Article ID Journal Published Year Pages File Type
4649888 Discrete Mathematics 2009 7 Pages PDF
Abstract

An edge of a kk-connected graph is said to be kk-contractible if its contraction results in a kk-connected graph. A kk-connected non-complete graph with no kk-contractible edge, is called contraction critical kk-connected. An edge of a kk-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree kk. Ando [K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Discrete Math. 293 (2005) 61–72] proved that a contraction critical 5-connected graph on nn vertices has at least n/2n/2 trivially noncontractible edges. Li [Xiangjun Li, Some results about the contractible edge and the domination number of graphs, Guilin, Guangxi Normal University, 2006 (in Chinese)] improved the lower bound to n+1n+1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on nn vertices has at least 32n trivially noncontractible edges.

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