### On the subdivided thorn graph and its metric dimension

#### Abstract

For some ordered subset *W* = {*w*_{1}, *w*_{2}, ⋯, *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*_{1}), *d*(*v*, *w*_{2}), ⋯, *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 *T**h*(*G*, *l*_{1}, *l*_{2}, ⋯, *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 *T**D*(*G*, *l*_{1}(*y*_{1}), *l*_{2}(*y*_{2}), ⋯, *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(*T**h*(*K*_{n}, *l*_{1}, *l*_{2}, ⋯, *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(*T**h*(*G*, *l*_{1}, *l*_{2}, ⋯, *l*_{n})), for arbitrary connected graph *G*. Next, the metric dimension of subdivided-thorn of complete graph, dim(*T**D*(*K*_{n}, *l*_{1}(*y*_{1}), *l*_{2}(*y*_{2}), ⋯, *l*_{n}(*y*_{n})) are determined and some conjectures for the lower bound of dim(*T**h*(*G*, *l*_{1}(*y*_{1}), *l*_{2}(*y*_{2}), ⋯, *l*_{n}(*y*_{n})) for arbitrary connected graph *G* are given.

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.19184/ijc.2019.3.1.4

#### References

J. Caceres, C. Hernando, M. Mora, I. Pelayo, M. Puertas and C. Seara, On the metric di- mension of some families of graphs, Electronic Notes in Discrete Mathematics, 22 (2005), 129–133.

G. Chartrand, L. Eroh, M. Johnson and O. Oellerman, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, 105 (2000), 99–113.

R. Diestel, Graph Theory, 4th ed., Springer-Verlag New York Inc., New York, 2010.

S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics, 70 (1996), 217–229.

F. Harary and R. A. Melter, On the metric dimension of a graph. Ars Combinatoria, 2 (1976), 191–195.

H. Iswadi, E. T. Baskoro and R. Simanjuntak, On the metric dimension of corona product of graphs, Far East J. Math. Sci. 52(2) (2011), 155–170.

H. Iswadi, E. T. Baskoro, R. Simanjuntak and A. N. M. Salman, The metric dimension of graph with pendant edges, Journal of Combin. Math. and Comb. Computing, 65 (2008), 139– 146.

S. W. Saputro, E. T. Baskoro, A. N. M. Salman and D. Suprijanto, The metric dimension of a complete n-partite graphs and its Cartesian product with a path, Journal of Combin. Math. and Comb. Computing, 71 (2009), 283–293.

B.Shanmukha,B.SooryanarayanaandK.S.Harinath, Metric dimension of wheels, Far East J. Appl. Math. 8(3) (2001), 217–229.

I. Tomescu and I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie Tome, 50(98) no 4 (2007), 371–376.

Z. P. Wang, Y. T. Zou, H. Y. Lin and Z. T. Wang, Graham’s pebbling conjecture on product of thorn graphs of complete graphs, Discrete Mathematics, 309 (2009), 3431–3435.

### Refbacks

- There are currently no refbacks.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.