The resolving number of a graph

MaRDI QIDQ5747415zbMATH OpenFDO

Authors Delia Garijo, Antonio González, A. Márquez

Publication date 14 February 2014

Full work available at URL https://arxiv.org/abs/1309.0252, https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2505/0.html

zbMATH Keywords

metric dimensionresolving numberresolving set

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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.

Recommendations

• On the metric dimension, the upper dimension and the resolving number of graphs
• Graphs of maximum and minimum order with fixed metric dimension and diameter
• Resolvability in graphs and the metric dimension of a graph
• scientific article; zbMATH DE number 6542389
• On certain resolving parameters of tree derived architectures

Cited in

(6)

• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• On the metric dimension, the upper dimension and the resolving number of graphs
• Strong resolving graph of a zero-divisor graph
• A new parameter on resolving sets with a realizable triple
• The independent resolving number of a graph
• scientific article; zbMATH DE number 6542389 (Why is no real title available?)

This page was built for publication: The resolving number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5747415)