Graceful Lobsters Obtained from Diameter Four Trees Using Partitioning Technique

Abstract

We view a lobster in this paper as below. A lobster with diameter at least five has a unique path $H=x_0,x_1,\dots ,x_m$ with the property that, besides the adjacencies in $H$, both $x_0$ and $x_m$ are adjacent to the centers of at least one $K_{i,s}$, where $s>0$, and each $x_i$, $1\le i\le m-1$, is at most adjacent to the centers of some $K_{1,s}$, where $s\ge 0$. This unique path $H$ is called the central path of the lobster. We call $K_{1,s}$ an even branch if $s$ is nonzero even, an odd branch if $s$ is odd, and a pendant branch if $s=0$. In this paper, we give graceful labelings to some new classes of lobsters with diameter at least five. In these lobsters, the degree of each vertex $x_i$, $0\le i\le m-1$, is even and the degree of $x_m$ may be odd or even, and we have one of the following features:

1. For some $t_1,t_2,t_3$, $0\le t_1<t_2<t_3\le m$, each $x_i$, $0\le i\le t_1$, is attached to two types (odd and pendant), or all three types, of branches; each $z_i$, $t_1+1\le i\le t_2$, is attached to all three types of branches; each $x_i$, $t_2+1\le i\le t_3$, is attached to two types of branches; and if $t_3<m$ then each $z_i$, $t_3+1\le i\le m$, is attached to one type (odd or even) of branch.
2. For some $t_1,t_2$, $0<t_1<t_2<m$, each $x_i$, $0\le i\le t_1$, is attached to two types (odd and pendant), or all three types, of branches; each $x_i$, $t_1+1\le i\le t_2$, is attached to two, or all three types of branches; and if $t_2<m$ then each $x_i$, $t_2+1\le i\le m$, is attached to one type (odd or even) of branch.
3. For some $t$, $0\le t\le m$, each $x_i$, $0\le i\le t$, is attached to all three types of branches; and if $t<m$ then each $x_i$, $t+1\le i\le m$, is attached to one type (odd or even) of branch.