DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


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: 2018-03-03, Revised: 2018-10-03, Accepted: 2018-10-03, https://doi.org/10.7151/dmgt.2178

Abstract:

By a $\big\{C_3^\alpha,C_6^\beta\big\}$-decomposition of a graph $G,$ we mean a partition of the edge set of $G$ into $\alpha$ cycles of length $3$ and $\beta$ cycles of length $6.$ In this paper, necessary and sufficient conditions for the existence of a $\big\{C_3^\alpha,C_6^\beta\big\}$-decomposition of $(K_m\times K_n)(\lambda),$ where $\times$ denotes the tensor product of graphs and $\lambda$ is the multiplicity of the edges, is obtained. In fact, we prove that for $\lambda\geq 1,$ $m,n\geq 3$ and $(m,n)\neq(3,3),$ a $\big\{C_3^\alpha,C_6^\beta\big\}$-decomposition of $(K_m\times K_n)(\lambda)$ exists if and only if $\lambda(m-1)(n-1)\equiv 0$ $($mod $2)$ and $3\alpha+6\beta=\frac{\lambda m(m-1)n(n-1)}{2}.$

Keywords:

cycle decomposition, tensor product

PDF
Close