A graceful labeling of a graph G of size n is an injective assignment of integers from {0, 1,..., n} 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 {1, 2,..., n}. 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 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 α-graph. In addition, we present a new family of graceful trees constructed using α-labeled caterpillars.
Barrientos, C., & Minion, S. (2016). Constructing Graceful Graphs with Caterpillars. Journal of Algorithms and Computation, 48(1), 117-125. doi: 10.22059/jac.2016.7946
MLA
Christian Barrientos; Sarah Minion. "Constructing Graceful Graphs with Caterpillars". Journal of Algorithms and Computation, 48, 1, 2016, 117-125. doi: 10.22059/jac.2016.7946
HARVARD
Barrientos, C., Minion, S. (2016). 'Constructing Graceful Graphs with Caterpillars', Journal of Algorithms and Computation, 48(1), pp. 117-125. doi: 10.22059/jac.2016.7946
VANCOUVER
Barrientos, C., Minion, S. Constructing Graceful Graphs with Caterpillars. Journal of Algorithms and Computation, 2016; 48(1): 117-125. doi: 10.22059/jac.2016.7946