(H1, H2)-SIM-SUPERMAGIC LABELINGS AND (H1| H2)-SUPERMAGIC LABELINGS OF SOME GRAPHS AND CERTAIN GRAPHS FORMED BY GRAPH OPERATIONS

• Main Author: Fadhilah Ashari, Yeva
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/71798
• Institution: Institut Teknologi Bandung

Let G and H be two simple and finite graphs. A graph G admits an H-covering if each edge of G belongs to a subgraph of G isomorphic to H. Then, a bijection f from the set of vertices union the set of edges V (G) ? E(G) to {1, 2, . . . , |V (G)| + |E(G)|} is called a total labeling of G. Let G be a graph admitting H-covering. A total labeling f of G is said to be an H-magic labeling if there exist a positive integer k such that w(H?) = P v?V (H?) f(v) + P e?E(H?) f(e) = k for each subgraph H? of G isomorphic to H. In this case, w(H?) is called a subgraphweight of H? and G is said to be H-magic. Moreover, the graph G and the labeling f are called H-supermagic and an H-supermagic labeling, respectively, if f(V (G)) = {1, 2, . . . , V (G)}. Let H1 and H2 be two simple and finite graphs. While working on H-magic labeling, we found a graph with a total labeling which is simultaneously H1- (super)magic and H2-(super)magic labelings. In the other side, we found a graph which is H1-(super)magic and H2-(super)magic, but there is no a total labeling of the graph that is simultaneously H1-(super)magic and H2-(super)magic labelings. Therefore, it is interesting to ask the existance of a total labeling of a graph which is simultaneously H1-(super)magic labeling and H2-(super)magic labeling. Hence, we introduce an (H1,H2)-sim-(super)magic labeling of graph. This concept is also motivated by a totally (anti)-magic labeling, a total labeling which is simultaneously an edge (anti)-magic total labeling and a vertex (anti)-magic total labeling. Let G? be a graph that simultaneously admits H1-covering and H2-covering. A total labeling f? of G? is called an (H1,H2)-sim-magic if f? is simultaneously an H1-magic labeling and an H2-magic labeling. Then, G? is called (H1,H2)-simmagic. If f?(V (G)) = {1, 2, . . . , |V (G)|}, G? and f? are called an (H1,H2)-simsupermagic and (H1,H2)-sim-supermagic labeling, respectively. In this thesis, we determine some forbidden subgraphs as the necessary conditions of a (K2,H)-simmagic graph where H is a path, star, or cycle. We also determine the sufficient conditions of an edge-supermagic graph to be (K2,H)-sim-supermagic. Moreover, we give the construction of an (H1,H2)-sim-supermagic labeling of graphs formed by join product and Cartesian product graph operations. Next, we also can verify that there exist a graph which does not admit H1-covering and H2-covering but each edge belongs to a subgraph isomorphic to H1 or H2. In this case, a graph G?? satisfying this condition is said to admit an (H1|H2)-covering. Motivated by this condition, we also introduced an (H1|H2)-(super)magic labeling of graph. Let G?? admits an (H1|H2)-covering. A total labeling f?? of G?? is called an (H1|H2)-magic if there exists two positive integers k1 and k2 such that w(H? P ) = v?V (H?) f(v) + P e?E(H?) f(e) = k1 for each subgraph H? of G?? isomorphic to H1 and subgraph-weight w(H??) = P v?V (H??) f(v) + P e?E(H??) f(e) = k2 for each subgraph H?? of G?? isomorphic to H2. In this thesis, we determine some forbidden subgraphs as the necessary conditions of (Cm|Sn)-magic graph for every 3 ? n < m. We also characterize an mH1 ? nH2 which is (H1|H2)-supermagic where H1 is not a subgraph of H2 and vice versa for |m?n| ? 1. By this result, we obtain a characterization of kCm ? lSn which is (Cm|Sn)-supermagic for |k ?l| ? 1. Furthermore, we give the construction of an (H1|H2)-supermagic labeling of graphs formed by total rooted product, subgraph amalgamation, and shackle.