کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653155 | 1632607 | 2006 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Some results on placing bipartite graphs of maximum degree two
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Bipartite graphs G=(L,R;E) and H=(L′,R′;E′) are bi-placeabe if there is a bijection f:L∪R→L′∪R′ such that f(L)=L′ and f(u)f(v)∉E′ for every edge uv∈E). We prove that if G and H are two bipartite graphs of order |G|=|H|=2p⩾4 such that the sizes of G and H satisfy ‖G‖⩽2p−3 and ‖H‖⩽2p−2, and the maximum degree of H is at most 2, then G and H are bi-placeable, unless G and H is one of easily recognizable couples of graphs.This result implies easily that for integers p and k1,k2,…,kl such that ki⩾2 for i=1,…,l and k1+…+k1⩽p−1 every bipartite balanced graph G of order 2p and size at least p2−2p+3 contains mutually vertex disjoint cycles C2k1,…,C2kl, unless G=K3,3−3K1,1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 24, 15 July 2006, Pages 285-289
Journal: Electronic Notes in Discrete Mathematics - Volume 24, 15 July 2006, Pages 285-289