On the Gracefulness of the Graph \(C_m\bigcup P_n\)

Abstract

On the gracefulness of graph \(C_m\bigcup P_n\), Frucht and Salinas that proved \(C_m\bigcup P_n\) is graceful and conjectured: \(C_m\bigcup P_n\) is graceful if and only if \(m+n=7\). In this paper, we prove graph \(C_m\bigcup P_n\) is graceful, for \(m=4k, n=k+2, k+3, 2k+1,\ldots, 2k+5;\) \(m=4k+1, n=2k, 3k+1, 4k+1;\) \(m=4k+2 n=3k, 3k+1,
4k+1; m=4k+3, n=2k+1, 3k, 4k\).