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

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

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

Citas

buscar en

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: 2014
Publicado en: Applied Mathematics and Computation, 249, 487-501.
Tipo de documento: Artículo
Resumen: 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.
Tamaño: 570.7Kb
Formato: PDF

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

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

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