New Families of Graceful Graphs

Abstract

In this paper, we show that if $G$ is an “$\alpha$-labeled” graph and if $H$ is a “pseudograceful” graph, then $G\cup H$ can be graceful or “pseudograceful” under some conditions on the $\alpha$-labeling function of $G$. This generalizes Theorem 2.1 of [21]. We also show that if $G$ is a Skolem-graceful, then $G+\overline{K_n}$ is graceful for all $n\ge 1$. We also give a partial answer to the question in [1] about the gracefulness of $\overline{K_n}+m{K}_2$ for $m\ge 3$. Finally, we complete the characterization of graceful graphs in the family $C_m\cup S_n$.