Graceful Labellings for an Infinite Class of Generalised Petersen Graphs

Abstract

Graceful labellings have both a mathematical beauty in their own right and considerable connections with pure and applied combinatorics (edge-decomposition of graphs, coding systems, communication networks, etc.). In the present paper, we exhibit a graceful labelling for each generalized Petersen graph $P_{8t,3}$ with $t\ge 1$. As a consequence, we obtain, for any fixed $t$, a cyclic edge-decomposition of the complete graph $K_{48t+1}$ into copies of $P_{8t,3}$. Due to its extreme versatility, the technique employed looks promising for finding new graceful labellings, not necessarily involving generalized Petersen graphs.