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,\dots ,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\le i\le m-1$, is at most adjacent to the centers of some $K_{1,s}$, $s\ge 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.