Some new classes of graceful Lobsters obtained from diameter four trees

Mishra, Debdas ; Panigrahi, Pratima

Mathematica Bohemica, Tome 135 (2010) no. 3, pp. 257-278.

Résumé

We observe that 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_{1, s}$, where $s > 0$, and each $x_i$, $1 \le i \le m - 1$, is adjacent at most to the centers of some $K_{1, s}$, where $s \ge 0$. This 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 the existing literature only some specific classes of lobsters have been found to have graceful labelings. Lobsters to which we give graceful labelings in this paper share one common property with the graceful lobsters (in our earlier works) that each vertex $x_i$, $ 0 \le i \le m - 1$, is even, the degree of $x_m$ may be odd or even. However, we are able to attach any combination of all three types of branches to a vertex $x_i$, $ 1 \le i \le m$, with total number of branches even. Furthermore, in the lobsters here the vertices $x_i$, $ 1 \le i \le m$, on the central path are attached up to six different combinations of branches, which is at least one more than what we find in graceful lobsters in the earlier works.

Détail

DOI : 10.21136/MB.2010.140703

Classification : 05C78
Keywords: graceful labeling; lobster; odd branch; even branch; inverse transformation; component moving transformation