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 \geq 1\). We also give a partial answer to the question in [1] about the gracefulness of \(\overline{K_n} + mK_2\) for \(m \geq 3\). Finally, we complete the characterization of graceful graphs in the family \(C_m \cup S_n\).