首页 | 本学科首页   官方微博 | 高级检索  
     


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 FiF and |E(FiH)|=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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号