Graphs with Metric Dimension Two-A Characterization

Authors: Sudhakara G, Hemanth Kumar A.R

Abstract:

In this paper, we define distance partition of vertex set of a graph G with reference to a vertex in it and with the help of the same, a graph with metric dimension two (i.e. β (G) = 2 ) is characterized. In the process, we develop a polynomial time algorithm that verifies if the metric dimension of a given graph G is two. The same algorithm explores all metric bases of graph G whenever β (G) = 2 . We also find a bound for cardinality of any distance partite set with reference to a given vertex, when ever β (G) = 2 . Also, in a graph G with β (G) = 2 , a bound for cardinality of any distance partite set as well as a bound for number of vertices in any sub graph H of G is obtained in terms of diam H .

Keywords: Metric basis, Distance partition, Metric dimension.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081979

References:

[1] Buckley F and Harary F, Distance in graphs, Addison - Wesley (1990).
[2] Christopher Poisson and Ping Zhang. The metric dimension of unicyclic graphs. J.Combin. Math. Combin. Comput., 40:17-32, 2002.
[3] F. Harary, Graph theory, Narosa/Addison Wesley (1969).
[4] Harary F and Melter R.A, On the metric dimension of a graph, Ars Combinatoria2 (1976), 191-195.
[5] Hartsfield Gerhard, Ringel, Pearls in Graph Theory, Academic press, USA (1994).
[6] Jos─ò C├íceres, Carmen Hernando, Merće Mora, Ignacio M. Pelayo, Mar├¼a. Puertas, Carlos Seara and David R. Wood, On the metric dimension of Cartesian product of graphs, arXiv: math.CO/0507527 v3 2 Mar 2006.
[7] Paul F. Tsuchiya, The landmark hierarchy; A new hierarchy for routing in very Large networks, ACM 0-89791-279-9/88/008/0035, 1988, page 35-42.
[8] Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks in graphs. Discrete Appl. Math., 70(3):217-229, 1996.
[9] Shanmukha B, Certain applications of number theory in graphs with emphases to networks. PhD. Thesis, 2003.
[10] Shanmukha B, Sooryanarayana B and Harinath K.S, Metric dimension of Wheels, FEJ. Appl. Math., 8(3)(2002), 217-229.
[11] Sooryanarayana B and Shanmukha B, A note on metric dimension, FEJ. Appl. Math., 5(3),(2001), 331-339.
[12] Sooryanarayana B, Certain combinatorial connections between groups, graphs and surfaces, PhD Thesis, 1998.
[13] Sooryanarayana B, On the metric dimension of a graph, Indian. J. Pure Appl. Math 29(4),(1998), 413 - 415 (2).
[14] Sooryanarayana B, K.S. Harinath and R.Murali, Some results on metric dimension of graph of diameter two,( communicated).