کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646812 1342314 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Some degree and forbidden subgraph conditions for a graph to have a kk-contractible edge
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Some degree and forbidden subgraph conditions for a graph to have a kk-contractible edge
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 1, 6 January 2016, Pages 207–216
نویسندگان
,