Article
Full entry |
PDF
(0.5 MB)
Feedback
PDF
(0.5 MB)
Feedback
Keywords:
graceful labeling; lobster; odd branch; even branch; inverse transformation; component moving transformation
graceful labeling; lobster; odd branch; even branch; inverse transformation; component moving transformation
Summary:
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.
References:
[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 0587620 | Zbl 0447.05032
[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 1683256
[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 0953.05067
[4] Hrnčiar, P., Haviar, A.: All trees of diameter five are graceful. Discrete Math. 233 (2001), 133-150. DOI 10.1016/S0012-365X(00)00233-8 | MR 1825608 | Zbl 0986.05088
[5] Mishra, D., Panigrahi, P.: Some new classes of graceful lobsters obtained from diameter four trees. (to appear) in Utilitus Mathematica. MR 2683638
[6] Mishra, D., Panigrahi, P.: Graceful lobsters obtained by component moving of diameter four trees. Ars Combinatoria 81 (October, 2006) 129-146. MR 2267807 | Zbl 1189.05154
[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 10.1016/j.camwa.2005.04.006 | MR 2165426
[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 1169.05374
[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 2414024
[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 0223271
[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 10.1016/0895-7177(94)00167-7 | MR 1302631 | Zbl 0814.05063
Search
Partner of
