Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6420820 | Applied Mathematics and Computation | 2014 | 15 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Delia Garijo, Antonio González, Alberto Márquez,