Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646812 | Discrete Mathematics | 2016 | 10 Pages |
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
Kiyoshi Ando,