Constant time calculation of the metric dimension of the join of path graphs

Abstract

The distance between two vertices of a simple connected graph G, denoted as (Formula presented.), is the length of the shortest path from u to v and is always symmetrical. An ordered subset (Formula presented.) of (Formula presented.) is a resolving set for G, if for ∀ (Formula presented.), there exists (Formula presented.) ∋ (Formula presented.). A resolving set with minimal cardinality is called the metric basis. The metric dimension of G is the cardinality of metric basis of G and is denoted as (Formula presented.). For the graph (Formula presented.) and (Formula presented.), their join is denoted by (Formula presented.). The vertex set of (Formula presented.) is (Formula presented.) and the edge set is (Formula presented.). In this article, we show that the metric dimension of the join of two path graphs is unbounded because of its dependence on the size of the paths. We also provide a general formula to determine this metric dimension. We also develop algorithms to obtain metric dimensions and a metric basis for the join of path graphs, with respect to its symmetries.