Closed trail decompositions of some classes of regular graphs

详细信息    查看全文

• 作者：P. Paulraja ; ^{pprajaau@sify.com} ; S. Sampath Kumar ^{ssamkumar.2008@gmail.com}
• 关键词：Closed trail decomposition ; Tensor product ; Wreath product ; Hamilton cycle ; Intersection graph
• 刊名：Discrete Mathematics
• 出版年：2012
• 出版时间：6 April, 2012
• 年：2012
• 卷：312
• 期：7
• 页码：1353-1366
• 全文大小：378 K

文摘

If are edge-disjoint subgraphs of such that , then we say that decompose . If each , then we say that decomposes and we denote it by . If each is a closed trail, then the decomposition is called a closed trail decomposition of . In this paper, we consider the decomposition of a complete equipartite graph with multiplicity , that is, , into closed trails of lengths , where is an odd prime number or is equal to the number of edges of the graph and denotes the wreath product of graphs. A similar result is also proved for , where ¡Á denotes the tensor product of graphs, if there exists a -cycle decomposition of the graph. We obtain the following corollary: if divides the number of edges of the even regular graph , then it has a -decomposition, where denotes a closed trail of length . For , this corollary subsumes the main results of the papers [A. Burgess, M. ?ajna, Closed trail decompositions of complete equipartite graphs, J. Combin. Des. 17 (2009) 374-403]; [B.R. Smith, Decomposing complete equipartite graphs into closed trails of length , Graphs Combin. 26 (2010) 133-140]. We have also partially obtained some results on -decomposition of .