Snakes and Caterpillars in Graceful Graphs

Graceful labelings use a prominent place among dier- ence vertex labelings. In this work we present new fam- ilies of graceful graphs all of them obtained applying a general substitution result. This substitution is ap- plied here to replace some paths with some trees with a more complex structures. Two caterpillars with the same size are said to be analogous if the larger stable sets, in both caterpillars, have the same cardinality. We study the conditions that allow us to replace, within a gracefully labeled graph, some snakes (or paths) by anal- ogous caterpillars, to produce a new graceful graph. We present ve families of graphs where this replacement is feasible, generalizing in this way some existing results: subdivided trees, rst attachment trees, path-like trees, two-point unio‎n of paths, and armed crowns.