Some New Classes of Graceful Lobsters Obtained by
Applying Inverse and Component Moving Transformations

Debdas Mishra; Pratima Panigrahi

doi:https://doi.org/10.14445/22315373/IJMTT-V2I1P504

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 2 | Issue 1 | Year 2011 | Article Id. IJMTT-V2I1P504 | DOI : https://doi.org/10.14445/22315373/IJMTT-V2I1P504

Some New Classes of Graceful Lobsters Obtained by Applying Inverse and Component Moving Transformations

Debdas Mishra, Pratima Panigrahi

Citation :

Debdas Mishra, Pratima Panigrahi, "Some New Classes of Graceful Lobsters Obtained by Applying Inverse and Component Moving Transformations," International Journal of Mathematics Trends and Technology (IJMTT), vol. 2, no. 1, pp. 1-11, 2011. Crossref, https://doi.org/10.14445/22315373/IJMTT-V2I1P504

Abstract

We observe that a lobster with diameter at least five has a unique path H = x0x1 . . . xm with the property that besides the adjacencies in H both x0 and xm are adjacent to the centers of at least one K1,s, where s > 0, and each xi , 1 ≤ i ≤ m−1, is at most adjacent to the centers of some K1,s, where s ≥ 0. This unique path H is called the central path of the lobster. We call K1,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 which the degree of each vertex xi , 0 ≤ i ≤ m−1, on the central path is even and the degree of the vertex xm may be odd or even. The lobsters appear in [5] also possess this property. However, in the lobsters of [5], at most the vertex x0 is attached to a combination of all three types of branches, whereas in this paper, we give graceful labelings to the lobsters in which not only the vertex x0 but also some (or all) xi , 1 ≤ i ≤ m, may exhibit this property.

Keywords

graceful labeling, lobster, odd and even branches, inverse transformation, component moving transformation

References

[1] J. C. Bermond, Radio antennae and French windmills, Graph Theory and Combinatorics, In Research Notes in Maths, (ed. R.J. Wilson), 34 (1979), 18 - 39.
[2] W. C. Chen, H. I. Lu, Y. N. Yeh, Operations of interlaced trees and graceful trees, Southeast Asian Bulletin of Mathematics 4 (1997), 337 - 348.
[3] J. A. Gallian, A dynamic survey of graph labeling, Electronic Journal of Combinatorics, DS6, Eleventh edition, February 29, 2008. url: http://www.combinatorics.org/Surveys/.
[4] P. Hrn ˇc iar, A. Havier, All trees of diameter five are graceful, Discrete Mathematics 233 (2001), 133 - 150.
[5] D. Mishra, P. Panigrahi, Graceful lobsters obtained by component moving of diameter four trees, Ars Combinatoria (81) (October, 2006), 129 - 147.
[6] D. Morgan, All lobsters with perfect matchings are graceful, Technical Report, University of Alberta, TR05-01, Jan 2005. url: http://www.cs.ualberta.ca/research /techreports/2005.php.
[7] H. K. Ng, Gracefulness of a class of lobsters, Notices AMS, 7(1986), abstract no. 825-05-294.
[8] G. Ringel, Problem 25 in theory of graphs and applications, Proceedings of Symposium Smolenice 1963, Prague Publishing House of Czechoslovak Academy of Science (1964), 162.
[9] J. G. Wang, D. J. Jin, X. G. Lu, D. Zhang, The gracefulness of a class of lobster trees, Mathematical and Computer Modelling 20(9) (1994), 105 - 110.