B. Sooryanarayana, Shreedhar K. and Narahari N.

Notes on Number Theory and Discrete Mathematics

Print ISSN 1310–5132, Online ISSN 2367–8275

Volume 22, 2016, Number 4, Pages 82—95

**Download full paper: PDF, 263 Kb**

## Details

### Authors and affiliations

B. Sooryanarayana

*Dept. of Mathematical & Computational Studies, Dr. Ambedkar Institute of Technology
Bengaluru, Karnataka State, India, Pin 560 056*

Shreedhar K.

*Dept. of Mathematics, K. V. G. College of Engineering
Sullia, Dakshina Kannada, Karnataka State, India, Pin 574 327*

Narahari N.

*Dept. of Mathematics, University College of Science, Tumkur University
Tumakuru, Karnataka State, India, Pin 572 103*

### Abstract

A resolving set of a graph *G* is a set *S* ⊆ *V*(*G*), such that, every pair of distinct vertices of *G* is resolved by some vertex in S. The metric dimension of *G*, denoted by *β*(*G*), is the minimum cardinality of all the resolving sets of G. Shamir Khuller et al. [10], in 1996, proved that a graph *G* with *β*(*G*) = 2 can have neither *K*_{5} nor *K*_{3,3} as its subgraph. In this paper, we obtain a forbidden subgraph, other than *K*_{5} and *K*_{3,3}, for a graph with metric dimension two. Further, we obtain the metric dimension of the total graph of some graph families. We also establish a Nordhaus–Gaddum type inequality involving the metric dimensions of a graph and its total graph and obtain the metric dimension of the line graph of the two dimensional grid *P _{m}* ×

*P*.

_{n}### Keywords

- Metric Dimension
- Landmarks

### AMS Classification

- 05C56

### References

- Buckley, F., & Harary, F. (1990) Distance in Graphs, Addison-Wesley.
- Brigham, R. C., Chartrand, G., Dutton, R. D., & Zhang, P. (2003) Resolving domination in graphs, Math. Bohem., 128(1), 25–36.
- Cantor, D. G. (1964) Determining a set from the cardinalities of its intersections with other sets, Canad. J. Math., 16, 94–97.
- Cantor, D. G., & Mills, W. H. (1966) Determination of a subset from certain combinatorial properties, Canad. J. Math., 18, 42–48.
- Chartrand, G., Erwin, D., Harary, F., & Zhang, P. (2000) Radio Antipodal Colorings of Cycles, Congr. Numer., 144, 129–141.
- Chartrand, G., & Zhang, P. (2003) The theory and applications of resolvability in graphs. A survey. In: Proc. 34th South Eastern International Conf. on Combinatorics, Graph Theory and Computing, vol. 160 of Congr. Numer., 47–68.
- Guy, R. K., & Nowakowski, R. J. (1995) Coin-weighing problems, Amer. Math. Monthly, 102(2), 164.
- Harary, F., & Melter, R. A. (1976) On the Metric dimension of a graph, Ars Combinatoria, 2, 191–195.
- Hernando, C., Mora, M., Pelayo, I. M., & Seara, C. (2010) Extremal Graph Theory for Metric Dimension and Diameter, The Electronic Journal of Combinatorics, 17.
- Khuller, S., Raghavachari, B., & Rosenfeld, A. (1996) Landmarks in graphs, Disc. Appl. Math., 70, 217–229.
- Slater, P. J. (1975) Leaves of trees, In: Proc. 6th South Eastern Conf. on Combinatorics, Graph Theory, and Computing, Vol. 14 of Congressus Numerantium: 549–559.
- Nordhaus, E. A., & Gaddum, J.W. (1956) On complementary graphs, Amer. Math. Monthly, 63, 175–177.
- Shanmukha, B., Sooryanarayana, B., & Harinath, K. S. (2002) Metric dimension of wheels, Far East J. Appl. Math., 8(3), 217–229.
- Saenpholphat, V., & Zhang, P. (2004) On connected resolving decompositions in graphs, Czechoslovak Math. J., 54(129)(3), 681–696.
- Shreedhar, K., Sooryanarayana, B., Hegde, C., & Vishukumar, M. (2010) Metric dimension of Hexogonal Cellular Networks, Int. J. of Math. Sci. and Engg. Applications, 4(XI), 133–148.
- Sooryanarayana, B. (1998) On the metric dimension of graph, Indian J. Pure Appl. Math, 29(4),413–415.
- Sooryanarayana, B. (2012) k-metric dimension of a graph, SIAM Conference of Discrete Mathematics, Dalhousie University, Halifax, Canada, 45.
- Sooryanarayana, B., & Shanmukha, B. (2001) A note on metric dimension, Far East J. Appl. Math., 5(3), 331–339.
- Sooryanarayana, B., & Geetha, K. N. (2014) On the k-metric dimension of graphs, Journal of Mathematical and Computational Science, 4(5), 861–878.

## Related papers

## Cite this paper

Sooryanarayana, B., Shreedhar K. & Narahari N. (2016). On the metric dimension of the total graph of a graph, Notes on Number Theory and Discrete Mathematics, 22(4), 82-95.