Constant Time Calculation of the Metric Dimension of the Join of Path Graphs

The distance between two vertices of a simple connected graph G, denoted as d(u, v), is the length of the shortest path from u to v and is always symmetrical. An ordered subset W = {w(1), w(2), w(3), . . . , w(k)} of V(G) is a resolving set for G, if for for all u,v is an element of V(G), there exists w(i) is an element of W (sic) d(u, w(i)) not equal d(v, w(i)). 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 dim(G). For the graph G(1) = (V-1, E-1,) and G(2) = (V-2, E-2), their join is denoted by G(1) + G(2). The vertex set of G(1) + G(2) is V-1 boolean OR V-2 and the edge set is E = E-1 boolean OR E-2 boolean OR {uv, u is an element of V-1, v is an element of V-2}. 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.

Automated summary

This article investigates the metric dimension and metric basis of a simple connected graph, and provides a method to determine them. It also explores the metric dimension of the join of two path graphs and develops algorithms to obtain metric dimensions and metric basis for such graphs.