Total views : 166

Some New Graceful Lobsters with Pendant Vertices with Central Paths


  • C. V. Raman College of Engineering, Bidyanagar, Mahura, Janla, Bhubaneswar – 752 054, Orissa,, India
  • College of Engineering and Technology, Ghatikia, Kalinga Nagar, Bhubaneswar – 751003, Odisha,, India
  • Bhadrak (Autonomous) College, Jaganathpur, Baudpur Village, Bhadrak, Odisha – 756100,, India


The objective of this article is to give graceful labeling to some new classes of lobsters in a bid to resolve the three and half decade old Bermond’s conjecture that all lobsters are graceful. Here we use the method of component moving transformation such as the transfer of the first and second type and the derived transformations such as BD8TF, 1JTF, and 2JTF for generating graceful trees from a given one. In a bid to resolve Bermond’s conjecture here we give graceful labelings to many classes of lobsters possessing at least one of the two distinct features from those found in the literature as detailed below. 1.The central paths of the lobsters contain one or more vertices which do not have any neighbour apart from those on the central path. 2.One or more vertices of the central paths are attached to leaves. 3. The vertices on the central path may be attached to any of the fifteen different combination of odd, even, and pendant branches.


AMS classification: 05C78, BD8TF, Graceful Labeling, Lobster, Odd and Even Branches, Transfers of the First and Second Type, 1JTF, 2JTF

Full Text:

 |  (PDF views: 129)


  • Ringel G. Problem 25 in theory of graphs and applications. Proceedings of Symposium SmolenicePrague Publishing House of Czechoslovak Academy of Science; 1964. p. 162.
  • Bermond JC. Radio antennae and French windmills. Editor Wilson RJ. Graph Theory and Combinatorics, In Research Notes in Maths. 1979; 34(2–3):18–39.
  • Chen WC, Lu HI, Yeh YN. Operations of interlaced trees and graceful trees. Southeast Asian Bulletin of Mathematics. 1997; 21(4):337–48.
  • Gallian JA. A dynamic survey of graph labelling. Electronic Journal of Combinatorics. 2015 Dec 17; DS6(18):5–408.
  • Hrnˇciar AP, Havier H. All trees of diameter _ve are graceful. Discrete Mathematics. 2001; 233(1):133–50. https://doi. org/10.1016/S0012-365X(00)00233-8
  • Mishra DAC, Panda P. Some new transformations and their applications involving graceful tree labelling. InternationalJournal of Mathematical Sciences and Engineering Applications. 2013; 7(1):239–54.
  • Mishra D, Panda AC, Dash RV. A class of graceful lobsters with even number of branches incident on the central path. International Journal of Mathematical Sciences and Applications. 2011; 1(2):463–72.
  • Mishra D, Panigrahi P. Some new classes of graceful lobsters obtained by applying inverse and component moving transformations. International Journal of Mathematics Trends and Technology (IJMTT). 2011; 1(2):6–16.
  • Mishra D, Panigrahi P. Some new classes of graceful lobsters obtained from diameter four trees. Mathematica Bohemica. 2010; 135(3):257–78.
  • Mishra D, Panigrahi P. A new class of graceful lobsters obtained from diameter four trees. Utilitus Mathematica. 2009; 3(3):183–209.
  • Mishra D, Panigrahi P. Some graceful lobsters with all three types of branches incident on the vertices of the central path. Computers and Mathematics with Applications. 2008; 56(5):1382–94. j.camwa.2008.02.034
  • Mishra D, Panigrahi P. Graceful lobsters obtained by component moving of diameter four trees. ARS Combinatoria. 2006; 81(3–4):129–46.
  • Morgan D. All lobsters with perfect matchings are graceful. Electronic Notes in Discrete Mathematics. 2002 Jul; 11:503–8.
  • Ng HK. Gracefulness of a class of lobsters. Notices AMS. 1986; 50(3–4):367–80.
  • Panigrahi P, Mishra D. Larger graceful and interlaced lobsters obtained by joining smaller ones. Southeast Asian Bulletin of Mathematics. 2009; 33:509–25.
  • Wang JG, Jin DJ, Lu XG, Zhang D. The gracefulness of a class of lobster trees. Mathematical and Computer Modelling. 1994; 20(9):105–10. 0895-7177(94)00167-7
  • Ulaganathan PP, Thirusangu K, Selvam B. Graceful and Skolem graceful labeling in extended duplicate graph of path. Indian Journal of Science and Technology. 2011 Feb; 4(2):1–5.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.