P4k-1-factorization of bipartite multigraphs

被引:3
作者
Wang Jian
Du Beiliang [1 ]
机构
[1] Suzhou Univ, Dept Math, Suzhou 215006, Peoples R China
[2] Nantong Vocat Coll, Nantong 226007, Peoples R China
来源
SCIENCE IN CHINA SERIES A-MATHEMATICS | 2006年 / 49卷 / 07期
关键词
bipartite multigraph; factor; factorization;
D O I
10.1007/s11425-006-0961-4
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let lambda K-m,K-n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P-upsilon-factorization of lambda K-m,K-n is a set of edge-disjoint P-upsilon-factors of lambda K-m,K-n which partition the set of edges of lambda K-m,K-n. When upsilon is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P-upsilon-factorization of lambda K-m,K-n. When upsilon is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for upsilon = 3. In this paper we will show that the conjecture is true when upsilon = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of lambda K-m,K-n is (1) (2k - 1)m <= 2kn, (2) (2k - 1)n <= 2km, (3) m + n equivalent to 0 (mod 4k - 1), (4) lambda(4k - 1)mn/[2(2k - 1)(m + n)] is an integer.
引用
收藏
页码:961 / 970
页数:10
相关论文
共 9 条
[1]  
Bondy J.A., 2008, GRAD TEXTS MATH
[2]   The proof of Ushio's conjecture concerning path factorization of complete bipartite graphs [J].
Du, BL ;
Wang, J .
SCIENCE IN CHINA SERIES A-MATHEMATICS, 2006, 49 (03) :289-299
[3]   P4k-1-factorization of complete bipartite graphs [J].
Du, BL ;
Wang, J .
SCIENCE IN CHINA SERIES A-MATHEMATICS, 2005, 48 (04) :539-547
[4]  
DU BL, 2000, AUSTR J COMBIN, V21, P197
[5]   G-DESIGNS AND RELATED DESIGNS [J].
USHIO, K .
DISCRETE MATHEMATICS, 1993, 116 (1-3) :299-311
[6]   P3-FACTORIZATION OF COMPLETE BIPARTITE GRAPHS [J].
USHIO, K .
DISCRETE MATHEMATICS, 1988, 72 (1-3) :361-366
[7]   P(2P)-FACTORIZATION OF A COMPLETE BIPARTITE GRAPH [J].
WANG, H .
DISCRETE MATHEMATICS, 1993, 120 (1-3) :307-308
[8]  
Wang J, 2003, UTILITAS MATHEMATICA, V63, P213
[9]   DESIGN OF A NEW BALANCED FILE ORGANIZATION SCHEME WITH LEAST REDUNDANCY [J].
YAMAMOTO, S ;
IKEDA, H ;
SHIGEEDA, S ;
USHIO, K ;
HAMADA, N .
INFORMATION AND CONTROL, 1975, 28 (02) :156-175