Graceful Lobsters Obtained by Component Moving of Diameter Four Trees

Abstract

We observe that a lobster with diameter at least five has a unique path \(x_0, x_1, \ldots, x_{m}\) (called the central path) such that \(x_p\) and \(x_m\) are adjacent to the centers of at least one \(K_{1,s}\), \(s > 0\), and besides adjacencies in the central path each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), \(s \geq 0\). In this paper we give graceful labelings to some new classes of lobsters with diameter at least five, in which the degree of the vertex \(x_m\) is odd and the degree of each of the remaining vertices on the central path is even. The main idea used to obtain these graceful lobsters is to form a diameter four tree \(T(L)\) from a lobster \(L\) of certain type, give a graceful labeling to \(T(L)\) and finally get a graceful labeling of \(L\) by applying component moving and inverse transformations.