Some graceful lobsters with all three types of branches incident on the vertices of the central path

摘要

We observe that a lobster having diameter at least five has a unique path H = x_0 x_1...x_m satisfying the property that, besides the adjacencies in H, both x_0 and x_m are adjacent to the centers of at least one K_(1,s), where s > 0, and each x_i, for 1 ≤ i ≤ m - 1, is at most adjacent to the centers of some K_(1,s), where s > 0. This unique path H is called the central path of the lobster. We call K_(1,s) an even branch if s is even and s ≠ 0, an odd branch if s is odd, and a pendant branch if s = 0. In this paper, we give graceful labelings to the lobsters having one of the following features. Let l_1, l_2, and l_3 be integers such that 1 ≤ l_1 < l_2 ≤ l_3 ≤ m. (1) The vertex x_0 is attached to an even number of odd branches and an odd number of pendant branches. Each vertex x_i. for 1 ≤ i ≤ l_1, is attached to some combination consisting of odd and pendant branches, whereas each vertex x_i, for l_1 + 1 ≤ i ≤ l_2, is attached to some combination consisting of all three types of branches. If l_2 < m, then we have one of the following properties. (ⅰ) Each vertex x_i for l_2 + 1 ≤ i ≤ l_3, is attached to some combination consisting of odd and even branches and each of the rest of the vertices x,, if any, is attached to only odd (or even) branches. (ⅱ) Each vertex x_i, for l_2 + 1 ≤ i ≤ l_3, is attached to some combination consisting of odd (respectively, even) and pendant branches. Each of the rest of the vertices x_i, if any, is attached to only odd (respectively, even) branches. (2) The vertex x_0 is attached to an even number of odd branches and an odd number of pendant branches and combinations of branches incident on the vertices x,, for 1 ≤ i ≤ m, are the subcases of those mentioned in (1), where one or more combinations are absent.