کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649095 | 1342442 | 2010 | 8 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Mathematics - Volume 310, Issue 22, 28 November 2010, Pages 3080–3087