BEBERAPA ALGORITMA PELABELAN GRACEFUL UNTUK GRAF CATERPILLAR

Main Article Content

Regina N Pakpahan
Patricia V. J Runtu
Meidy Atina Kuron

Abstract

Graceful labeling, first introduced by Rosa as β-labeling. A graceful labeling (or β-labeling) on a graph G involves assigning labels to its set of vertices, forming an injective function f that maps each vertex to the set of non-negative integers {0, 1, 2, ..., |E(G)|}, where |E(G)| denotes the number of edges in G. This induces a bijective function f* that maps the edges of G to the set of positive integers {1,2,...,|E(G)|} which the edges label obtained by absolute number of the subtraction between 2 neighboring vertex labels. One renowned conjecture proposed by Kotzig-Ringel-Rosa, known as the Graceful Tree Conjecture (GTC), posits that all trees are graceful. To this day, this remains an open problem, challenging researchers to substantiate its validity. The quest for graceful labeling, particularly for specific types of trees, continues to be an active zona of research. Notably, caterpillar graphs have been established as graceful. It is worth noting that not all graphs possess a unique labeling. For instance, in the case of graceful labeling for caterpillar graphs, there exist four distinct methods, which will be elucidated algorithmically in this article. By demonstrating various approaches to labeling caterpillar graphs, it is hoped that this concept can be extended to other graceful labelings, ultimately contributing to the identification of more graceful trees

Article Details

How to Cite
Pakpahan, R., Runtu, P., & Kuron, M. (2023). BEBERAPA ALGORITMA PELABELAN GRACEFUL UNTUK GRAF CATERPILLAR. SOSCIED, 6(1), 296-302. https://doi.org/10.32531/jsoscied.v6i1.690
Section
Articles

References

Rosa, A. (1967). On certain valuations of the vertices of a graph. Jurnal Theory of Graphs, Proc. Internat. Symposium,Rome, 1966, Gordonand Breach, N.Y. and Dunod Paris, pp. 349–355.

N. Parvathi & S. Vidyanandini (2014) Graceful Labeling of a Tree from Caterpillars, Journal of Information and Optimization Sciences, 35:4, 387-393, DOI: 10.1080/02522667.2014.961811

G, Ringel. (1963). Theory of graphs and its applications, Proceedings of the Symposium Smolenice. held in Smolenice in June, 1963. New York, pp. 85–90.

Hossain, F., Aziz, M.A., & Kaykobad, M. (2014) New Classes of Graceful trees, Journal of Discrete Mathematics, vol. 2014, Article ID 194759, 6 pages. DOI: 10.1155/2014/194759

Haviar, M., Ivaska, M. (2014). Vertex Labellings of Simple Graph. Research and Exposition in Mathematics. Banska Bystrica (34) pp. 72–74.

M. M. Al Aziz, M. F. Hossain, T. Faequa and M. Kaykobad,. (2014). Graceful labeling of trees: Methods and applications. 17th International Conference on Computer and Information Technology (ICCIT), Dhaka, Bangladesh, 2014. pp. 92-95. DOI: 10.1109/ICCITechn.2014.7073154.

Sugeng, K.A., Slamet, S., Silaban, D.R. (2014). Teori Graf dan Aplikasinya. Depok: Departemen Matematika FMIPA UI.

Sugiyono. (2012). Metode Penelitian Kuantitatif, Kualitatif, dan R&D. Bandung: Alfabeta.

Zed, M. (2008). Metode Penelitian Kepustakaan. Jakarta : Yayasan Obor Indonesia.

Mirzaqon. T, A dan Budi Purwoko. (2017). Studi Kepustakaan Mengenai Landasan Teori dan Praktik Konseling Expressive Writing. Jurnal BK Unesa, 8(1).
Abstract viewed = 94 times
PDF downloaded = 90 times