Decomposition of Complete Graphs and Complete Bipartite Graphs Into $\alpha$-Labelled Trees

Abstract

Let $G$ be a graph with $r$ vertices of degree at least two. Let $H$ be any graph. Consider $r$ copies of $H$. Then $G\oplus H$ denotes the graph obtained by merging the chosen vertex of each copy of $H$ with every vertex of degree at least two of $G$. Let $T_0$ and $T^{A_1}$ be any two caterpillars. Define the first attachment tree $T_1=T_0\oplus T^{A_1}$. For $i\ge 2$, define recursively the $(i^{th})$ attachment tree $T_i=T_{i-1}\oplus T^{A_i}$, where $T_{i-1}$ is the $(i-1{)}^{th}$ attachment tree. Here one of the penultimate vertices of $T^{A_1}$, $i\ge 1$ is chosen for merging with the vertices of degree at least two of $T_{i-1}$, for $i\ge 1$. In this paper, we prove that for every $i\ge 1$, the $i$th attachment tree $T_i$ is graceful and admits a $\beta$-valuation. Thus it follows that the famous graceful tree conjecture is true for this infinite class of $(i^{th})$ attachment trees $T_i^{\prime }s$, for all $i\ge 1$. Due to the results of Rosa $[21]$ and El-Zanati et al. $[5]$ the complete graphs $K_{2cm+1}$ and complete bipartite graphs $K_{qm,pm}$, for $c,p,m,q\ge 1$ can be decomposed into copies of $i$th attachment tree $T_i$, for all $i\ge 1$, where $m$ is the size of such $i$th attachment tree $T_i$.