On σ -Tripartite Labelings of Odd Prisms and Even Möbius Ladders

Abstract

© 2017, Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia. A common question in the study of graph decompositions is when does a graph G decompose the complete graph or the complete graph with a 1-factor removed or added. It is known that a σ-tripartite labeling of a tripartite graph G with n edges can be used to obtain a cyclic G-decomposition of K 2nt+1 for every positive integer t. Moreover, it can be used to obtain a cyclic G-decomposition of both K 2nt+2 - I and K 2nt + I, where I is a 1-factor. We show that if G is an odd prism on 10 or more vertices or an even Möbius ladder, then G admits a σ-tripartite labeling.