On the metric dimension of the total graph of a graph

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
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₅ nor K_3,3 as its subgraph. In this paper, we obtain a forbidden subgraph, other than K₅ 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

1. Buckley, F., & Harary, F. (1990) Distance in Graphs, Addison-Wesley.
2. Brigham, R. C., Chartrand, G., Dutton, R. D., & Zhang, P. (2003) Resolving domination in graphs, Math. Bohem., 128(1), 25–36.
3. Cantor, D. G. (1964) Determining a set from the cardinalities of its intersections with other sets, Canad. J. Math., 16, 94–97.
4. Cantor, D. G., & Mills, W. H. (1966) Determination of a subset from certain combinatorial properties, Canad. J. Math., 18, 42–48.
5. Chartrand, G., Erwin, D., Harary, F., & Zhang, P. (2000) Radio Antipodal Colorings of Cycles, Congr. Numer., 144, 129–141.
6. 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.
7. Guy, R. K., & Nowakowski, R. J. (1995) Coin-weighing problems, Amer. Math. Monthly, 102(2), 164.
8. Harary, F., & Melter, R. A. (1976) On the Metric dimension of a graph, Ars Combinatoria, 2, 191–195.
9. Hernando, C., Mora, M., Pelayo, I. M., & Seara, C. (2010) Extremal Graph Theory for Metric Dimension and Diameter, The Electronic Journal of Combinatorics, 17.
10. Khuller, S., Raghavachari, B., & Rosenfeld, A. (1996) Landmarks in graphs, Disc. Appl. Math., 70, 217–229.
11. 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.
12. Nordhaus, E. A., & Gaddum, J.W. (1956) On complementary graphs, Amer. Math. Monthly, 63, 175–177.
13. Shanmukha, B., Sooryanarayana, B., & Harinath, K. S. (2002) Metric dimension of wheels, Far East J. Appl. Math., 8(3), 217–229.
14. Saenpholphat, V., & Zhang, P. (2004) On connected resolving decompositions in graphs, Czechoslovak Math. J., 54(129)(3), 681–696.
15. 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.
16. Sooryanarayana, B. (1998) On the metric dimension of graph, Indian J. Pure Appl. Math, 29(4),413–415.
17. Sooryanarayana, B. (2012) k-metric dimension of a graph, SIAM Conference of Discrete Mathematics, Dalhousie University, Halifax, Canada, 45.
18. Sooryanarayana, B., & Shanmukha, B. (2001) A note on metric dimension, Far East J. Appl. Math., 5(3), 331–339.
19. Sooryanarayana, B., & Geetha, K. N. (2014) On the k-metric dimension of graphs, Journal of Mathematical and Computational Science, 4(5), 861–878.