Metric-locating-dominating partitions in graphs

A partition ? = { S 1 ,...,S k } of the vertex set of a connected graph G is a metric-locating partition of G if for every pair of vertices u,v belonging to the same part S i , d ( u,S j ) 6 = d ( v,S j ), for some other part S j . The partition dimension s p ( G ) is the minimum cardinality of a metric- locating partition of G . A metric-locating partition ? is called metric-locating-dominanting if for every vertex v of G , d ( v,S j ) = 1, for some part S j of ?. The partition metric-location-domination number ? p ( G ) is the minimum cardinality of a metric-locating-dominating partition of G . In this paper we show, among other results, that s p ( G ) = ? p ( G ) = s p ( G ) + 1. We also charac- terize all connected graphs of order n = 7 satisfying any of the following conditions: ? p ( G ) = n - 1, ? p ( G ) = n - 2 and s p ( G ) = n - 2. Finally, we present some tight Nordhaus-Gaddum bounds for both the partition dimension s ( G ) and the partition metric-location-domination number ? ( G ). Keywords: dominating partition, locating partition, location, domination, metric location