Constructing Graceful Graphs with Caterpillars

Abstract

A graceful labeling of a graph <em>G</em> of size <em>n</em> is an injective assignment of integers from {0, 1,...,<em> n</em>} to the vertices of <em>G</em>, such that when each edge of <em>G</em> has assigned a weight, given by the absolute di erence of the labels of its end vertices, the set of weights is {1, 2,..., <em>n</em>}. If a graceful labeling <em>f</em> of a bipartite graph <em>G</em> assigns the smaller labels to one of the two stable sets of <em>G</em>, then <em>f</em> is called an -labeling and <em>G</em> is said to be an <em>α</em>-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 union of a cycle and a caterpillar. We present necessary conditions for this union to be graceful and, in the case where the cycle has even size, to be an <em>α</em> -graph. In addition, we present a new family of graceful trees constructed using <em>α</em>-labeled caterpillars.