The Graceful Coalescence of Alpha Cycles

Abstract

The standard coalescence of two graphs is extended, allowing to identify two isomorphic subgraphs instead of a single vertex. It is proven here that any succesive coalescence of cycles of size $n$, where $n$ is divisible by four, results in an $\alpha$-graph, that is, the most restrictive kind of graceful graph, when the subgraphs identified are paths of sizes not exceeding $\frac{n}{2}$. Using the coalescence and another similar technique, it is proven that some subdivisions of the ladder $L_n = P_2 \times P_n$ also admit an $\alpha$-labeling, extending and generalizing the existing results for this type of subdivided graphs.