Folding trees gracefully

Abstract

When a graceful labeling of a bipartite graph assigns the smaller labels to the vertices of one of the stable sets of the graph, the assignment is called an α-labeling. Any graph that admits such a labeling is an α-graph. In this work we extend the concept of vertex amalgamation to generate a new class of α-graphs obtained by a sequence of k-vertex amalgamations of t copies of an α-tree. This procedure is also applied to any collection of α-trees such that any pair of trees in this collection have stable sets with the same cardinalities. We also use this idea on other types of α-graphs. In addition, we present a family of α-trees of even diameter formed with four caterpillars of the same size.

Keywords

• α-labeling
• graceful labeling
• k-vertex amalgamation