کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420130 | 683896 | 2007 | 5 صفحه PDF | دانلود رایگان |
Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F1,F2,…,FmF1,F2,…,Fm is called an F-factorization of G orthogonal to H if Fi≅FFi≅F and |E(Fi∩H)|=1|E(Fi∩H)|=1 for each i=1,2,…,mi=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K4k,4kK4k,4k has a C4C4-factorization orthogonal to H provided that H is a k -factor of K4k,4kK4k,4k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r⩾kr⩾k, Kkr2,kr2Kkr2,kr2 has a Kr,rKr,r-factorization orthogonal to H if H is a k -factor of Kkr2,kr2Kkr2,kr2; (3) K2d2,2d2K2d2,2d2 has a C4C4-factorization such that each edge of H belongs to a different C4C4 if H is a subgraph of K2d2,2d2K2d2,2d2 with maximum degree Δ(H)⩽dΔ(H)⩽d.
Journal: Discrete Applied Mathematics - Volume 155, Issue 3, 1 February 2007, Pages 400–404