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 \geq 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 \geq 1\) is chosen for merging with the vertices of degree at least two of \(T_{i-1}\), for \(i \geq 1\). In this paper, we prove that for every \(i \geq 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’_is\), for all \(i \geq 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 \geq 1\) can be decomposed into copies of \(i\)th attachment tree \(T_i\), for all \(i \geq 1\), where \(m\) is the size of such \(i\)th attachment tree \(T_i\).