Decomposition of bipartite graphs into special subgraphs |
| |
Authors: | Guantao Chen Richard H. Schelp |
| |
Affiliation: | a Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA b Faculty of Mathematics and Statistics, Central China Normal University, Wuhan 430079, China c Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, USA |
| |
Abstract: | Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F1,F2,…,Fm is called an F-factorization of G orthogonal to H if Fi≅F and |E(Fi∩H)|=1 for each i=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K4k,4k has a C4-factorization orthogonal to H provided that H is a k-factor of K4k,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?k, Kkr2,kr2 has a Kr,r-factorization orthogonal to H if H is a k-factor of Kkr2,kr2; (3) K2d2,2d2 has a C4-factorization such that each edge of H belongs to a different C4 if H is a subgraph of K2d2,2d2 with maximum degree Δ(H)?d. |
| |
Keywords: | Factorization Orthogonal Complete bipartite graphs |
本文献已被 ScienceDirect 等数据库收录! |
|