Document Type : Research Paper

Authors

• Christian Barrientos ¹
• Sarah M Minion ²

¹ Department of Mathematics, Valencia College, Orlando, FL, 32825, USA.

² Department of Mathematics, Valencia College, Orlando, FL, 32825, USA

Abstract

Graceful labelings use a prominent place among difference vertex labelings. In this work we present new families of graceful graphs all of them obtained applying a general substitution result. This substitution is applied here to replace some paths with some trees with a more complex structures. Two caterpillars with the same size are said to be \textit{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 analogous caterpillars, to produce a new graceful
graph. We present five families of graphs where this replacement is
feasible, generalizing in this way some existing results: subdivided trees, first attachment trees, path-like trees, two-point union of paths, and armed crowns.

Keywords

• \a-labeling
• graceful labeling
• snake
• caterpillar. & & \\ %\vspace{0.1cm} \end{tabular}