Constructing Graceful Graphs with Caterpillars

A graceful labeling of a graph G of size n is an injective assignment of integers from f0; 1; : : : ; ng to the vertices of G, such that when each edge of G has assigned a weight, given by the absolute dierence of the labels of its end vertices, the set of weights is f1; 2; : : : ; ng. If a graceful labeling f of a bipartite graph G assigns the smaller labels to one of the two stable sets of G, then f is called an -labeling and G is said to be an -graph. A tree is a caterpillar if the deletion of all its leaves results in a path. In this work we study graceful labelings of the disjoint unio‎n of a cycle and a caterpillar. We present necessary conditions for this unio‎n to be graceful and, in the case where the cycle has even size, to be an - graph. In addition, we present a new family of graceful trees constructed using -labeled caterpillars.