MAGIC DOMINATING SETS OF GRAPHS

• Main Author: Ali Hasan, M.
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/65100
• Institution: Institut Teknologi Bandung

A multiset representation rm(v|W) of a vertex v in a graph G with respect to a subset W ? V (G) is a multiset of distances between v and all vertices in W. If rm(v|W) is distinct for every v in V (G), W is called an m?resolving set of G. The smallest cardinality of an m?resolving set of G is called the multiset dimension of G, denoted by md(G). A subset W ? V (G) is called a dominating set of G if every vertex in V (G) \W is adjacent to at least one vertex inW. The smallest cardinality of a dominating set of G is called the domination number of G, denoted by ?(G). Motivated by seeing the opposite nature of the m?resolving set concept, we present a new notion called a magic dominating set where all vertices outside have an equal multiset representation. This set is truly related to dominating set of the graph itself. An interesting optimization problem is to discover the minimum magic dominating set or equivalently to achieve the maximum number of all vertices outside having the same multiset representation. Therefore, we define a magic domination number of G, denoted by ?m(G), as the minimum cardinality of a magic dominating set of G. In this research, we provide the bounds of ?m(G) for any graph G. We also characterize graphs whose certain magic domination numbers. Besides that, for any positive integers k and n with n ? 3 and and 1 ? k ? n ? 1, we show the existence of a graph G of order n such that ?m(G) = k. Additionally, we determine the magic domination numbers of some classes of graphs.