Article ID Journal Published Year Pages File Type
4649095 Discrete Mathematics 2010 8 Pages PDF
Abstract

J.A. Gallian has proved [J.A. Gallian, Labeling prisms and prism related graphs, Congr. Numer. 59 (1987) 89–100] that every cubic graph M2kM2k obtainable from a 2k2k-cycle by adding its kk diameters (the so-called Moebius Ladder   of order 2k2k) is graceful. Here, in the case of kk even, we propose a new graceful labeling that besides being simpler than Gallian’s one is able to give, at the same time, a graceful labeling of the prism of order 2k2k. Most importantly in the case of kk odd, namely in the bipartite case, we prove that M2kM2k also admits an αα-labeling. This implies that there exists a cyclic decomposition of the complete graph K6kt+1K6kt+1 into copies of M2kM2k for every pair of positive integers kk and tt with kk odd.In some cases we are able to give such decompositions also when kk is even. Apart from the case of t=1t=1 that is an obvious consequence of the gracefulness of M2kM2k, this happens, for instance, when k≡2k≡2 (mod 4) and 6kt+16kt+1 is a prime.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,