Determining number versus metric dimension of graphs
by
Carlos Seara
Dept. Matematica Aplicada II, Politechnical University of Catalonia, Spain
Coauthors: José Cáceres, Delia Garijo, Maria L. Puertas

We initiate a study on the problem of computing the difference between the metric dimension and the determining number of graphs. We provide new proofs and results on the determining number of trees and Cartesian products of graphs, and establish some lower bounds on the difference between the two parameters.

A set of vertices S is a determining set of a finite, connected, simple graphG if every automorphism of G is uniquely determined by its action on S. The determining number is the smallest size of a determining set. Determining sets are frequently used to identify the automorphism group of a graph. They are obtained by using its connection with another well-known parameter of graphs: the metric dimension or location number.

A set of vertices S ⊆ V(G) resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices of S. A resolving set S of minimum cardinality is a metric basis, and |S| is the metric dimension of G. Resolving sets arise in several areas including coin weighing problems, network discovery and verification, robot navigation, connected joins in graphs, and strategies for Mastermind game.

The main purpose of this talk is to answer the following question: Can the difference between the determining number and the metric dimension of a graph of order n be arbitrarily large? This question turns out to be interesting since an automorphism preserves distances and resolving sets are determining sets. It arises first as an open problem by D. Boutin, and its answer has led us to a number of results on the determining number of some families of graphs in which the metric dimension is known.

Date received: March 28, 2008