| Popis: |
Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F"1,F"2,...,F"m is called an F-factorization of G orthogonal to H if F"i@?F and |E(F"i@?H)|=1 for each i=1,2,...,m. Gyarfas and Schelp conjectured that the complete bipartite graph K"4"k","4"k has a C"4-factorization orthogonal to H provided that H is a k-factor of K"4"k","4"k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r>=k, K"k"r"^"2","k"r"^"2 has a K"r","r-factorization orthogonal to H if H is a k-factor of K"k"r"^"2","k"r"^"2; (3) K"2"d"^"2","2"d"^"2 has a C"4-factorization such that each edge of H belongs to a different C"4 if H is a subgraph of K"2"d"^"2","2"d"^"2 with maximum degree @D(H)= |
Full Text from ScienceDirect