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
Authors and affiliations
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. , in 1996, proved that a graph G with β(G) = 2 can have neither K5 nor K3,3 as its subgraph. In this paper, we obtain a forbidden subgraph, other than K5 and K3,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 Pm × Pn.
- Metric Dimension
- 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.
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.