TY - JFULL
AU - Sudhakara G and Hemanth Kumar A.R
PY - 2009/1/
TI - Graphs with Metric Dimension Two-A Characterization
T2 - International Journal of Mathematical and Computational Sciences
SP - 1127
EP - 1133
VL - 3
SN - 1307-6892
UR - https://publications.waset.org/pdf/13897
PU - World Academy of Science, Engineering and Technology
NX - Open Science Index 36, 2009
N2 - 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 .
ER -