#TITLE_ALTERNATIVE#

• Main Author: AGUNG GEDE NGURAH (NIM 30104006), ANAK
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/7181
• Institution: Institut Teknologi Bandung

An edge-magic total labeling on a graph with p vertices and q edges is a one-toone map taking the vertices and edges onto the integers 1, 2, 3, p + q with the property that for each edge the sum of the label on the edge and the labels of its endpoints is constant. Since its introduction by Kotzig and Rosa in 1970, this labeling becomes one of the most famous graph labelings that have been studied by many researchers. Enomoto, Llado, Nakamigawa and Ringel studied this labeling by introducing the terminology of the super edge-magic total labeling, namely an edge-magic total labeling with an additional property that all vertices receive the p smallest labels. On the other hand, the extension and variation of these labelings have been introduced. Their applications have also been studied, such as in cryptography where edge-magic total labelings are used in a construction of a secret sharing scheme.<p> <br /> <br /> <br /> The classification of graphs that admit a (super)edge-magic total labeling is an interesting topic for researchers. Some classes of graphs had been proved admitting these labeling. However, there still remain many open problems such as the conjectures which state that every tree admits an edge-magic total labeling and every tree admits a super edge-magic total labeling. Motivated by these conjectures, some researchers studied these labelings for particular types of trees. Additionally, some classes of graphs had been proved not admitting these labelings. Concerning to this fact, the concepts (super) edge-magic deficiencies of a graph were introduced. These concepts measure how close a graph with a (super) edge-magic graph is.<p> <br /> <br /> <br /> In this dissertation, we study and give partial solutions to these two problems, namely classification of graphs that admit a (super) edge-magic total labeling and determination of (super) edge-magic deficiency of some classes of graphs. For the first problem, we consider (super) edge-magic total labeling for some classes of graphs such as path-like-trees, fire crackers, lobsters, and chain graphs. Also, we propose methods to construct new (super)edge-magic graphs from old ones. From these methods we can obtain new classes of (super) edge-magic graphs; some of the resulting <br /> <br /> <br /> graphs support the correctness of the conjectures that every tree has a (super)edge-magic total labeling. For the second problem, we study the deficiencies of particular type of graphs such as chain graphs, fans, double fans, wheels, disconnectedbipartite graphs, and multipartite graphs.