New families of graceful banana trees (Q1126331)

Let \(G= (V,E)\) be a graph with \(p\) vertices and \(q\) edges. An injective map \(\phi\) from \(V\) into \(\{0,1, \dots, q\}\) is called a graceful labeling of \(G\) if the induced map \(\Phi\) from \(E\) into \(\{1,2, \dots, q\}\), defined by \(\Phi (e) = |\phi (u)- \phi(v) |\) for \(e= uv\), is surjective. If a graceful labeling of a graph \(G\) exists, \(G\) is called a graceful graph. A conjecture due to Ringel and Kotzig is that all trees are graceful. This conjecture is still open. A banana tree is one obtained from a family of stars by joining one end-vertex of each star to a new vertex. In the paper a new family of banana trees is defined and it is shown that the trees in this family are graceful.