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

Abstract (VO)

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

Bibliographie

[1] Bermond, J. C.: Graceful graphs, radio antennae and French windmills. Graph Theory and Combinatorics, Proc. Conf. Notes in Maths. 34 (1979), 18-37. | MR | Zbl

[2] Chen, W. C., Lu, H. I., Yeh, Y. N.: Operations of interlaced irees and graceful trees. Southeast Asian Bull. Math. 21 (1997), 337-348. | MR

[3] Gallian, J. A.: A dynamic survey of graph labeling. Electronic Journal of Combinatorics, DS6, Eleventh edition, February 29, 2008.\hfil url: http://www.combinatorics.org/Surveys/ | Zbl

[4] Hrnčiar, P., Haviar, A.: All trees of diameter five are graceful. Discrete Math. 233 (2001), 133-150. | DOI | MR | Zbl

[5] Mishra, D., Panigrahi, P.: Some new classes of graceful lobsters obtained from diameter four trees. (to appear) in Utilitus Mathematica. | MR

[6] Mishra, D., Panigrahi, P.: Graceful lobsters obtained by component moving of diameter four trees. Ars Combinatoria 81 (October, 2006) 129-146. | MR | Zbl

[7] Mishra, D., Panigrahi, P.: Graceful lobsters obtained by partitioning and component moving of diameter four trees. Computers and Mathematics with Applications 50 (August 2005) 367-380. | DOI | MR

[8] Morgan, D.: All lobsters with perfect matchings are graceful. Technical Report, University of Alberta, TR05-01, Jan 2005.\hfil url: http://www.cs.ualberta.ca/research/techreports/2005.php | Zbl

[9] Ng, H. K.: Gracefulness of a class of lobsters. Notices AMS 7 (1986), abstract no. 825-05-294.

[10] Panigrahi, P., Mishra, D.: Graceful lobsters obtained from diameter four trees using partitioning technique. Ars Combinatoria 87 (April, 2008) 291-320. | MR

[11] Ringel, G.: Problem 25 in theory of graphs and applications. Proceedings of Symposium Smolenice 1963, Academia (1964), 162.

[12] Rosa, A.: On certain valuations of the vertices of a graph. Theórie des Graphes, (ed. P. Rosenstiehl), Dunod, Paris (1968), 349-355. | MR

[13] Wang, J. G., Jin, D. J., Lu, X. G., Zhang, D.: The gracefulness of a class of lobster trees. Math. Comput. Modelling 20 (1994), 105-110. | DOI | MR | Zbl