کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872233 | 681647 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Packing bipartite graphs with covers of complete bipartite graphs
ترجمه فارسی عنوان
بسته بندی گرافیک دو طرفه با پوشش گرافیک دو طرفه کامل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
For a set S of graphs, a perfect S-packing (S-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of S and that together contain all vertices of G. If G allows a covering (locally bijective homomorphism) to a graph H, i.e., a vertex mapping f:VGâVH satisfying the property that f(u)f(v) belongs to EH whenever the edge uv belongs to EG such that for every uâVG the restriction of f to the neighborhood of u is bijective, then G is an H-cover. For some fixed H let S(H) consist of all connected H-covers. Let Kk,â be the complete bipartite graph with partition classes of size k and â, respectively. For all fixed k,ââ¥1, we determine the computational complexity of the problem that tests whether a given bipartite graph has a perfect S(Kk,â)-packing. Our technique is partially based on exploring a close relationship to pseudo-coverings. A pseudo-covering from a graph G to a graph H is a homomorphism from G to H that becomes a covering to H when restricted to a spanning subgraph of G. We settle the computational complexity of the problem that asks whether a graph allows a pseudo-covering to Kk,â for all fixed k,ââ¥1.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 40-50
Journal: Discrete Applied Mathematics - Volume 168, 11 May 2014, Pages 40-50
نویسندگان
Jérémie Chalopin, Daniël Paulusma,