Opened Access The resolving number of a graph
Cites
Show item statistics
Icon
Export to
Author: Garijo Royo, Delia
González Herrera, Antonio
Márquez Pérez, Alberto
Department: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Date: 2013
Published in: Discrete Mathematics & Theoretical Computer Science 15(3): 155-166 (2013)
Document type: Article
Abstract: 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.
Size: 302.2Kb
Format: PDF

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

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)