Gracefulness of \(P_{2r,2m}\)

Abstract

The graph \(P_{a,b}\) is defined as the one obtained by taking \(b\) vertex-disjoint copies of the path \(P_{a+1}\) of length \(a\), coalescing their first vertices into one single vertex labeled \(u\) and then coalescing their last vertices into another single vertex labeled \(v\). K.M. Kathiresan showed that \(P_{2r,2m-1}\) is graceful and conjectured that \(P_{a,b}\) is graceful except when \((a,b) = (2r+1, 4s+2)\). In this paper, an algorithm for finding another graceful labeling of \(P_{2r,2}\) is provided, and \(P_{2r,2(2k+1)}\) is proved to be graceful for all positive \(r\) and \(k\).