Article ID Journal Published Year Pages File Type
420130 Discrete Applied Mathematics 2007 5 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,