**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**31100

##### 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 dimension,
Metric Basis,
Distance partition

**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).