ALGORITMA PELABELAN GRACEFUL UNTUK GRAF BINTANG MULTI-LEVEL

Abstract

Graph theory is a topic in mathematics that is still relatively new and developing rapidly. Graph theory is used to simplify and solving problems like connection, networking, travelling or flow. One of the very interesting topics in graph theory is graph labeling. 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. The Graceful Tree Conjecture (GTC) posits that all trees can be gracefully labeled, a hypothesis still unproven. The quest for graceful labeling, particularly for specific types of trees, continues to be an active zona of research. One of the graph that already proven can be labeled with graceful labeling is star graph. Now we gonna prove graceful labeling for star graph, if each leaf in the star graph is connected to m new leaves. We call it multi-level star graph. Exploring these methods aims to extend the concept to other graphs, contributing to the identification of more gracefully labeled trees.