C_4 decomposition of the tensor product of complete graphs
Abstract
Let G be a simple and finite graph. A graph is said to be decomposed into subgraphs H1 and H2 which is denoted by G = H1 ⊕ H2, if G is the edge disjoint union of H1 and H2. If G = H1 ⊕ H2 ⊕ H3 ⊕ ... ⊕ Hk, where H1, H2, H3, ..., Hk are all isomorphic to H, then G is said to be H-decomposable. Futhermore, if H is a cycle of length m then we say that G is Cm-decomposable and this can be written as Cm|G. Where G × H denotes the tensor product of graphs G and H, in this paper, we prove the necessary and sufficient conditions for the existence of C4-decomposition of Km × Kn. Using these conditions it can be shown that every even regular complete multipartite graph G is C4-decomposable if the number of edges of G is divisible by 4.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.2
References
A. D. Akwu and O. Oyewumi, C6 decomposition of the tensor product of complete graphs, J. Combin. Math. Combin. Comput., In Press.
B. Alspach and H. Gavlas, Cycle decompositions of Kn and Kn I, J. Combin. Theory Ser. B 81 (2001), 77-99.
E.J. Billington, Decomposing complete tripartite graphs into cycles of length 3 and 4, Dis- crete Math. 197/198 (1999), 123–135.
E.J. Billington, D.G. Hoffman and B.M. Maenhaut, Group divisible pentagon systems, Util. Math. 55 (1999), 211–219.
N.J. Cavenagh and E.J. Billington, Decompositions of complete multipartite graphs into cy- cles of even length, Graphs Combin. 16 (2000), 49–65.
J. Fahnenstiel and D. Froncek, Decomposition of complete graphs into connected unicyclic bipartite graphs with eight edges, Electron. J. Graph Theory Appl. 7(2)(2019), 235–250.
D. G. Hoffman, C. C. Linder and C. A. Rodger, On the construction of odd cycle systems, J. Graph Theory 13 (1989), 417–426.
I. Heinrich and M. Streicher, Cycle decompositions and constructive characterizations, Electron. J. Graph Theory Appl. 7(2)(2019), 411–428.
T.P. Kirkman, On a problem in combinations, Cambridge and Dublin Math. J. 2 (1847), 191–204.
J. Ma, L. Pu and H. Shen, Cycle decomposition of Kn,n I, SIAM J. Discrete Math. 20 (2006), 603–609.
R.S. Manikandan and P. Paulraja, Cp-decompositions of some regular graphs, Discrete Math. 306 (2006), 429–451.
R.S. Manikandan and P. Paulraja, C5-decompositions of the tensor product of complete graphs, Australas. J. Combin. 37 (2007), 285–293.
R.S. Manikandan and P. Paulraja, Hamilton cycle decompositions of the tensor product of complete multipartite graphs, Discrete Math. 308 (2008), 3586–3606.
R.S. Manikandan and P. Paulraja, C7-decompositions of the tensor product of complete graphs, Discuss. Math. Graph Theory 37 (2017), 523–535.
A. Muthusamy and P.Paulraja, Factorizations of product graphs into cycles of uniform length, Graphs Combin. 11 (1995), 69–90.
P. Paulraja and S. S. Kumar, Resolvable even cycle decompositions of the tensor product of complete graphs. Discrete Math. 311 (2011), 1841–1850.
M. Sajna, Cycle decompositions III: complete graphs and fixed length cycles, J. Combin. Designs 10 (2002), 27–78.
D. Sotteau, Decomposition of Km,n - I into cycles (circuits) of length 2k, J. Combin. Theory (Series B), 30 (1981), 75–81.
B. R. Smith, Decomposing complete equipartite graphs into cycles of length 2p, J. Combin. Des. 16 (2006), 244–252.
B. R. Smith, Complete equipartite 3p-cycle systems, Australas J. Combin. 45 (2009), 125– 138.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.