Opened Access The resolving number of a graph
Estadísticas
Icon
Exportar a
Autor: Garijo Royo, Delia
González Herrera, Antonio
Márquez Pérez, Alberto
Departamento: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Fecha: 2013
Publicado en: Discrete Mathematics & Theoretical Computer Science 15(3): 155-166 (2013)
Tipo de documento: Artículo
Resumen: We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: while computing the metric dimension of an arbitrary graph is known to be NP-hard, we show that the resolving number can be computed in polynomial time. We then relate the resolving number to classical graph parameters: diameter, girth, clique number, order and maximum degree. With these relations in hand, we characterize the graphs with resolving number 3 extending other studies that provide characterizations for smaller resolving number.
Tamaño: 302.2Kb
Formato: PDF

URI: http://hdl.handle.net/11441/38826

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones