A note on the metric dimension of subdivided thorn graphs

Lyra Yulianti, Narwen Narwen, Sri Hariyani


For some ordered subset W = {w1, w2, ⋯, wt} 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(vW) = {d(v, w1), d(v, w2), ⋯, d(v, wt)}. The set W is the resolving set of G if for every two vertices u, v in G, r(uW) ≠ r(vW). 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, l1, l2, ⋯, ln), is constructed from G by adding li leaves to vertex vi of G, for li ≥ 1 and 1 ≤ in. The subdivided-thorn graph, denoted by TD(G, l1(y1), l2(y2), ⋯, ln(yn)), is constructed by subdividing every li leaves of the thorn graph of G into a path on yi vertices. In this paper the metric dimension of thorn of complete graph, dim(Th(Kn, l1, l2, ⋯, ln)), li ≥ 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, l1, l2, ⋯, ln)), for arbitrary connected graph G. Next, the metric dimension of subdivided-thorn of complete graph, dim(TD(Kn, l1(y1), l2(y2), ⋯, ln(yn)) are determined and some conjectures for the lower bound of dim(Th(G, l1(y1), l2(y2), ⋯, ln(yn)) for arbitrary connected graph G are given.


metric dimension; thorn-subdivided graphs; complete graph

Full Text:



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.

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


  • There are currently no refbacks.

ISSN: 2541-2205

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

View IJC Stats