The Gracefulness of Unions of Cycles and Complete Bipartite Graphs

Abstract

A graceful labeling of a graph $G$ of size $n$ is an assignment of labels from $\{0,1,\dots ,n\}$ to the vertices of $G$ such that when each edge has assigned a weight defined by the absolute difference of its end-vertices, the resulting weights are distinct. The gracefulness of a graph $G$ is the smallest positive integer $k$ for which it is possible to label the vertices of $G$ with distinct elements from the set $\{0,1,\dots ,k\}$ in such a way that distinct edges have distinct weights. In this paper, we determine the gracefulness of the union of cycles and complete bipartite graphs. We also give graceful labelings of unions of complete bipartite graphs.