DETERMINATION AND CHARACTERIZATION OF METRIK-LOCATION-DOMINATION NUMBER FOR SEVERAL CLASSES OF GRAPHS

• Main Author: Zulfaneti
• Format: Dissertations
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/79625
• Institution: Institut Teknologi Bandung

Let G = (V;E) be a simple, finite and connected graph. A set D V is said to be a dominating set of G if every vertex v 2 V ???? D is adjacent to a vertex in D. The minimum cardinality of the dominating set of G is called a domination number of G. The representation of a vertex v 2 V (G) with respect to a set R V is a distance vector of the vertex with respect to R. The set R is called a resolving set of G if every vertex in G has distinct representation with respect to R. The minimum cardinality of the resolving set of G is called metric dimension. Moreover, a dominating set which is also resolving set in G is called a metric-locating-dominating set of G. The concept of metric-location-domination number of a connected graph was first introduced by Brigham dkk. (2003). This concept is a combination of the concept of the domination number and the metric dimension. This combination of concepts sets of a study to search for a set which is a dominating set and also a resolving set. Brigham et al (2003) showed the relationship among the metric dimension (G), the domination number (G) and the metric-location-domination number M(G). They show that maxf (G); (G)g M(G) minf (G) + (G); n ???? 1g. This result provides lower and upper bounds of the metric-location-domination number of any graph G. Although we know the lower and upper bounds of the metric-location-domination number of any graph, determining the exact metric-location-domination number of a graph is a difficult problem. This is due to the wide variety of structures of graphs. Therefore, the study of metric-location-domination numbers is limited to certain graph families. Up to now, the known results are the characterization of graphs of order n with metric-location-domination number 1, n ???? 2 and n ???? 1. Determining the set of resolving dominating cannot be separated from the search for the dominating set and the resolving set of a graph. On a graph, if a resolving set is contained in a minimum dominating set then the minimum dominating set can be as a resolving set. Conversely, if a dominating set is contained in a minimum resolving set then the minimum resolving set can be as a dominating set. Therefore, for the graphs with this condition, the metric-location-domination number is the same as the lower bound, namely M(G) = maxf (G); (G)g. Meanwhile, if any minimum dominating set and any minimum resolving set do not intersect, the metric-domination-location number is same as the upper bound, that is M(G) = minf (G) + (G); n ???? 1g. In this disertation, we conduct a study on graphs with metric-location-domination number attaining lower bound or upper bound. In particular, we determine the metric-location-domination number of k-paths, corona graphs, and trees. Moreover, we also determine the sufficient or necessary conditions of corona graphs and trees with metric-location-domination number attaining lower bound or upper bound. In addition, we characterize graphs with small metric-location-domination number. More spesifically, we characterize all graphs with metric-location-domination number 2, all trees with metric-location-domination number 3, and all unicyclic graphs with metric-location-domination number 3. In this disertation, we also discuss graphs order n with metric-location-domination number half of its order. As it is known, the conditions of dominating set and resolving set have a significant influence to the metric-locating-dominating set of a graph. In the study, we focus on a certain class of a graph of order n satisfying M(G) = 1 2n.