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, \ldots, 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 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), where \(s \geq 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 \leq i \leq 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 \leq t_1 < t_2 < t_3 \leq m\), each \(x_i\), \(0 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(z_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to all three types of branches; each \(x_i\), \(t_2 + 1 \leq i \leq t_3\), is attached to two types of branches; and if \(t_3 < m\) then each \(z_i\), \(t_3 + 1 \leq i \leq 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 \leq i \leq t_1\), is attached to two types (odd and pendant), or all three types, of branches; each \(x_i\), \(t_1 + 1 \leq i \leq t_2\), is attached to two, or all three types of branches; and if \(t_2 < m\) then each \(x_i\), \(t_2 + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.
3. For some \(t\), \(0 \leq t \leq m\), each \(x_i\), \(0 \leq i \leq t\), is attached to all three types of branches; and if \(t < m\) then each \(x_i\), \(t + 1 \leq i \leq m\), is attached to one type (odd or even) of branch.