Decomposition of the Tensor Product of Complete Graphs into Cycles of Lengths 3 and 6

摘要

By a {C3α,?C3β} -decomposition of a graph G, we mean a partition of the edge set of G into α cycles of length 3 and β cycles of length.6. In this paper, necessary and sufficient conditions for the existence of a {C3α,?C3β} -decomposition of (Km × Kn)(λ), where × denotes the tensor product of graphs and λ is the multiplicity of the edges, is obtained. In fact, we prove that for λ ≥ 1, m, n ≥ 3 and (m, n) ≠ (3, 3), a {C3α,?C3β} -decomposition of (Km × Kn)(λ) exists if and only if λ(m ? 1)(n ? 1) ≡ 0 (mod 2) and 3α+6β=λm(m-1)n(n-1)2 .