4.5 Article

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

Journal

SYMMETRY-BASEL
Volume 15, Issue 3, Pages -

Publisher

MDPI
DOI: 10.3390/sym15030708

Keywords

metric dimension; metric basis; path graphs; join of graphs

Ask authors/readers for more resources

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.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.5
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available