کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4657232 | 1343725 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Removable cycles in non-bipartite graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we prove the following result. Suppose that s and t are vertices of a 3-connected graph G such that G−s−t is not bipartite and there is no cutset X of size three in G for which some component U of G−X is disjoint from {s,t}. Then either (1) G contains an induced path P from s to t such that G−V(P) is not bipartite or (2) G can be embedded in the plane so that every odd face contains one of s or t. Furthermore, if (1) holds then we can insist that G−V(P) is connected, while if G is 5-connected then (1) must hold and P can be chosen so that G−V(P) is 2-connected.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 99, Issue 1, January 2009, Pages 30-38
Journal: Journal of Combinatorial Theory, Series B - Volume 99, Issue 1, January 2009, Pages 30-38