On using distances to locate vertices: resolving sets and metric bases of graphs, two generalisations and their forced vertices

Abstract

A graph consists of vertices that are connected by edges. A resolving set of a graph is a subset of its vertices that gives a unique combination of distances to every vertex of the graph. We can use the distances we are given to locate a vertex within the graph we are considering. Resolving sets were introduced by Slater in 1975 and independently by Harary and Melter in 1976. Robot navigation and network discovery and verification are examples of applications that have been suggested for resolving sets.

In this dissertation, we consider resolving sets and two of their generalisations that can be used to locate subsets of vertices instead of individual vertices. We consider how these generalisations are connected to other concepts such as locatingdominating sets and the boundary of a graph. We place special emphasis on studying the minimum cardinalities of resolving sets and the two generalisations. In addition to proving general bounds to these minimum cardinalities, we consider their exact values in some graph families. Natural decision problems arise from some of the concepts that we consider and we study their algorithmic complexities.

We also investigate which vertices of a graph must be included in an optimal resolving set or one of the two generalisations. For the resolving sets that can be used to locate subsets of vertices, there exist vertices that are in all such resolving sets. We call these vertices forced vertices of the graph. Such vertices do not exist for regular resolving sets. However, for minimum resolving sets they can exist, and we call them basis forced vertices of the graph. In this dissertation, we characterise the forced vertices of a graph, and consider some extremal properties of graphs that contain basis forced vertices.