Gracefully Labeling Prisms

Jen-Hsin Huang1, Steven S.Skiena 1
1Department of Computer Science State University of New York Stony Brook, NY 11794

Abstract

We provide graceful labelings for prisms \(C_{2m} \times P_n\), with even cycles, for all \(n \geq 2\), and prisms \(C_{2m+1} \times P_n\), with odd cycles when \(3 \leq mn \leq 12\). Further, we verify that the windmill graph \(K^{(m)}_{4}\) is graceful for \(r \leq 22\), and that the square of a path \(P_n\) is graceful for \(n \leq 32\).