Graphs with Metric Dimension Two-A Characterization
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 .
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081979Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1430
 Buckley F and Harary F, Distance in graphs, Addison - Wesley (1990).
 Christopher Poisson and Ping Zhang. The metric dimension of unicyclic graphs. J.Combin. Math. Combin. Comput., 40:17-32, 2002.
 F. Harary, Graph theory, Narosa/Addison Wesley (1969).
 Harary F and Melter R.A, On the metric dimension of a graph, Ars Combinatoria2 (1976), 191-195.
 Hartsfield Gerhard, Ringel, Pearls in Graph Theory, Academic press, USA (1994).
 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.
 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.
 Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks in graphs. Discrete Appl. Math., 70(3):217-229, 1996.
 Shanmukha B, Certain applications of number theory in graphs with emphases to networks. PhD. Thesis, 2003.
 Shanmukha B, Sooryanarayana B and Harinath K.S, Metric dimension of Wheels, FEJ. Appl. Math., 8(3)(2002), 217-229.
 Sooryanarayana B and Shanmukha B, A note on metric dimension, FEJ. Appl. Math., 5(3),(2001), 331-339.
 Sooryanarayana B, Certain combinatorial connections between groups, graphs and surfaces, PhD Thesis, 1998.
 Sooryanarayana B, On the metric dimension of a graph, Indian. J. Pure Appl. Math 29(4),(1998), 413 - 415 (2).
 Sooryanarayana B, K.S. Harinath and R.Murali, Some results on metric dimension of graph of diameter two,( communicated).