BEBERAPA ALGORITMA PELABELAN GRACEFUL UNTUK GRAF CATERPILLAR

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