University of TehranJournal of Algorithms and Computation2476-277648120161225Constructing Graceful Graphs with Caterpillars1171257946ENChristianBarrientosDepartment of Mathematics, Clayton State University, Morrow, Georgia 30260, USASarahMinionDepartment of Mathematics, Clayton State University, Morrow, Georgia 30260, USAJournal Article20160605A 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 dierence 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.https://jac.ut.ac.ir/article_7946_ab86e4c77cafca0ee7fc0724a85925bb.pdf