Authors:
P. Paulraja, R. Srimathi
Title:
Decomposition of the tensor product of graphs into cycles of lengths 3 and 6
Source:
Discussiones Mathematicae Graph Theory
Received 03.03.2018, Revised 03.10.2018, Accepted 03.10.2018, doi: 10.7151/dmgt.2178

Abstract:
By a \big{C3α,C6β\big}-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 \big{C3α,C6β\big}-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 \big{C3α,C6β\big}-decomposition of (Km× Kn)(λ) exists if and only if λ(m-1)(n-1)≡ 0 (mod 2) and 3α+6β=\frac{λ m(m-1)n(n-1)}{2}.
Keywords:
cycle decomposition, tensor product

Links:
PDF