Advances and Applications in Discrete Mathematics
Volume 4, Issue 2, Pages 169 - 186
(October 2009)
|
|
GRAPHS WITH METRIC DIMENSION TWO - A CHARACTERIZATION
G. Sudhakara (India) and A. R. Hemanth Kumar (India)
|
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
We also find a bound for cardinality
of any distance partite set with reference to a given vertex, whenever
Also, in a graph G
with
a bound for cardinality of any
distance partite set as well as a bound for number of vertices in any subgraph H
of G is obtained
in terms of diam H.