P_5-FACTORIZATION OF CARTESIAN PRODUCT OF GRAPHS

摘要

Partition of G into edge-disjoint H-factors is called H-factorization of G. Muthusamy and Paulraja have conjectured that for k ≥ 3, K_m□K_n has a P_k-factorization if and only if. mn = 0 (mod k) and k(m+n — 2)≡ 0 (mod 2(k — 1))， where □ denote cartesian product of graphs. In this paper, it is shown that the necessary conditions mn ≡ 0 (mod 5) and 5(m + 1) = 0 (mod 8) are sufficient for the existence of a P_5-factorization of K_m?C_n when (i) m = 7, n = 0 (mod 5), (ii) m = 175 (mod 280), n = 0 (mod 5). Further, it is shown that the necessary conditions mn ≡ 0 (mod 5) and 5(m + n — 2) ≡ 0 (mod 8) are sufficient for the existence of a P_5-factorization of Km?K_n in the following cases: (i) ≡ 5 (mod 40), n ≡ 5 (mod 40), (ii) m ≡ 10 (mod 40), n ≡ 0 (mod 40), (iii) m ≡ 15 (mod 120),n = 3 and m ≡ 15 (mod 120), n ≡ 75 (mod 120), (iv) m ≡ 20 (mod 40), n ≡ 30 (mod 120), (V) m ≡ 25 (mod 40), n ≡ 25 (mod 40), (vi) m ≡ 30 (mod 120), n = 4 and m ≡ 30 (mod 120), n ≡ 20 (mod 40)，(vii) m ≡ 75 (mod 120), n ≡ 15 (mod 120), （viii） m ≡ 0 (mod 40)， n = 2 and m ≡ 0 (mod 40)， n ≡ 10 (mod 40). In fact our results partially answer the above conjecture when k = 5.