Metric-locating-dominating partitions in graphs
Visualitza/Obre
Tipus de documentReport de recerca
Data publicació2017-11-03
Condicions d'accésAccés obert
Llevat que s'hi indiqui el contrari, els
continguts d'aquesta obra estan subjectes a la llicència de Creative Commons
:
Reconeixement-NoComercial-SenseObraDerivada 3.0 Espanya
Abstract
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 ß 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 ß p ( G ) = ¿ p ( G ) = ß 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 ß p ( G ) = n - 2. Finally, we present some tight Nordhaus-Gaddum bounds for both the partition dimension ß ( G ) and the partition metric-location-domination number ¿ ( G ). Keywords: dominating partition, locating partition, location, domination, metric location
CitacióHernando, M., Mora, M., Pelayo, I. M. "Metric-locating-dominating partitions in graphs". 2017.
URL repositori externhttps://arxiv.org/pdf/1711.01086.pdf
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
metriclocatingdominatingpartitions in graphs.pdf | 384,3Kb | Visualitza/Obre |