Metric Dimension of Banded-Turán Graph

Abstract

Given a graph G=(V(G),E(G)). Let S={s1,...,sk} be an ordered subset of V(G). Consider a vertex x, a coordinate of x with respect to S is represented as r(x|S)=(d(x,s1),...,d(x,sk)) where d(x,si) equals the number of edges in the shortest path between x and si for i=1,...,k. The minimum value of k such that for every x has distinct coordinate is called metric dimension of G. Turán graph T(n,r), n>=r>=2  is a subgraph of complete r-partite graph on n vertices having property that the difference of cardinality of any two distinct classes is at most one. In this paper, we build a new graph namely a banded-Turán graph, BT(n,r,m), as a graph built by a Turán graph T(n,r) and r uniform path graphs Pm in which every vertex of each class of T(n,r) connected to an initial vertex of corresponding path graph Pm. Intuitively, this graph illustrates as if a Turán graph is banded by r uniform ropes. We determine some basic graph properties including independence number, chromatic number, and diameter of banded-Turán. The main result in this paper is we obtain that the metric dimension of banded-Turán turns out that it depends on the number of its classes. If it has two classes then the metric dimension is equal to n-1 and if it has more than two classes then the metric dimension is equal to the metric dimension of Turán graph included in it.