Ars Combinatoria · 2008 · 88 citations · 4 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationGraph AlgorithmsGraph TheoryMetric GeometryGraph DiameterGraph PartitioningMetric Graph TheoryMinimum DistanceMinimum Distance BoundsSet CardinalityVertex Distance
Given a graph G, we say S µ V (G) is resolving if for each pair of distinct u;v 2 V (G) there is a vertex x in S where d(u;x) 6 d(v;x). The metric dimension of G is the minimum cardinality of all resolving sets. For w 2 V (G), the distance from w to S, denoted d(w;S), is the minimum distance between w and the vertices of S. Given P = fP1;P2;:::;Pkg an ordered partition of V (G) we say P is resolving if for each pair of distinct u;v 2 V (G) there is a part Pi where d(u;Pi) 6 d(v;Pi). The partition dimension is the minimum order of all resolving partitions. In this paper we consider relationships between metric dimension, partition dimension, diameter, and other graph parameters. We construct \universal examples of graphs with given partition dimension, and we use these to provide bounds on various graph parameters based on metric and partition dimensions. We form † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † † ¢¢¢ ¢¢¢ ¢¢¢ † † † † † ¢¢¢ | }
4
Resolvability in graphs and the metric dimension of a graph
Gary Chartrand, Linda Eroh, Mark A. Johnson et al. · Discrete Applied Mathematics · 2000 · 982 citations
Samir Khuller, Balaji Raghavachari, Azriel Rosenfeld · Discrete Applied Mathematics · 1996 · 808 citations
The partition dimension of a graph
Gary Chartrand, Ebrahim Salehi, P. Zhang · Aequationes Mathematicae · 2000 · 249 citations