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 \geq 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.