A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs

作者：Li, Tingting^*; Su, Jianji

来源：Discrete Mathematics, 2009, 309(9): 2870-2876.

DOI：10.1016/j.disc.2008.07.020

• Trivially noncontractible edge
• Contraction critical
• 5-connected
• Fragment

An edge of a k-connected graph is said to be k-contractible if its contraction results in a k-connected graph. A k-connected non-complete graph with no k-contractible edge, is called contraction critical k-connected. An edge of a k-connected graph is called trivially noncontractible if its two end vertices have a common neighbor of degree k. 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 n vertices has at least n/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 1. In this paper, the bound is improved to the statement that any contraction critical 5-connected graph on n vertices has at least in trivially noncontractible edges.

• 出版日期2009-5-6
• 单位广西师范大学; 广西壮族自治区经济管理干部学院