On the subdivided thorn graph and its metric dimension

Abstract

For some ordered subset W = {w₁, w₂, ⋯, w_t} of vertices in connected graph G, and for some vertex v in G, the metric representation of v with respect to W is defined as the t-vector r(v∣W) = {d(v, w₁), d(v, w₂), ⋯, d(v, w_t)}. The set W is the resolving set of G if for every two vertices u, v in G, r(u∣W) ≠ r(v∣W). The metric dimension of G, denoted by dim(G), is defined as the minimum cardinality of W. Let G be a connected graph on n vertices. The thorn graph of G, denoted by Th(G, l₁, l₂, ⋯, l_n), is constructed from G by adding l_i leaves to vertex v_i of G, for l_i ≥ 1 and 1 ≤ i ≤ n. The subdivided-thorn graph, denoted by TD(G, l₁(y₁), l₂(y₂), ⋯, l_n(y_n)), is constructed by subdividing every l_i leaves of the thorn graph of G into a path on y_i vertices. In this paper the metric dimension of thorn of complete graph, dim(Th(K_n, l₁, l₂, ⋯, l_n)), l_i ≥ 1 are determined, partially answering the problem proposed by Iswadi et al . This paper also gives some conjectures for the lower bound of dim(Th(G, l₁, l₂, ⋯, l_n)), for arbitrary connected graph G. Next, the metric dimension of subdivided-thorn of complete graph, dim(TD(K_n, l₁(y₁), l₂(y₂), ⋯, l_n(y_n)) are determined and some conjectures for the lower bound of dim(Th(G, l₁(y₁), l₂(y₂), ⋯, l_n(y_n)) for arbitrary connected graph G are given.