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$.