Repositorio de producción científica de la Universidad de Sevilla

The difference between the metric dimension and the determining number of a graph

 

Advanced Search
 
Opened Access The difference between the metric dimension and the determining 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: 2014
Published in: Applied Mathematics and Computation, 249, 487-501.
Document type: Article
Abstract: We study the maximum value of the difference between the metric dimension and the determining number of a graph as a function of its order. We develop a technique that uses functions related to locating-dominating sets to obtain lower and upper bounds on that maximum, and exact computations when restricting to some specific families of graphs. Our approach requires very diverse tools and connections with well-known objects in graph theory; among them: a classical result in graph domination by Ore, a Ramsey-type result by Erdős and Szekeres, a polynomial time algorithm to compute distinguishing sets and determining sets of twin-free graphs, k-dominating sets, and matchings.
Size: 570.7Kb
Format: PDF

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

DOI: http://dx.doi.org/10.1016/j.amc.2014.10.034

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

This item appears in the following Collection(s)