Article ID Journal Published Year Pages File Type
4646812 Discrete Mathematics 2016 10 Pages PDF
Abstract

An edge in a kk-connected graph is said to be kk-contractible if the contraction of the edge results in a kk-connected graph. We say that a kk-connected graph GG satisfies “mm-degree-sum condition” if ∑x∈V(W)degG(x)≥mk+1∑x∈V(W)degG(x)≥mk+1 hold for any connected subgraph WW of GG with |W|=m|W|=m. Let kk be an integer such that k≥5k≥5. We prove that if a kk-connected graph GG with neither K1+C4K1+C4 nor K2+(K1∪K2)K2+(K1∪K2) satisfies 3-degree-sum condition, then GG has a kk-contractible edge. We also prove that if a kk-connected graph GG with no K1+P4K1+P4 satisfies 4-degree-sum condition, then GG has a kk-contractible edge.

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