Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On the determining number and the metric dimension of graphs. | On the determining number and the metric dimension of graphs Jose Caceres Department of Statistics and Applied Mathematics University of Almería Almería Spain j caceres@ Delia Garijo Department of Applied Mathematics I University of Seville Seville Spain dgarijo@ Maria Luz Puertas Department of Statistics and Applied Mathematics University of Almería Almería Spain mpuertas@ Carlos Seara t Department of Applied Mathematics II Universitat Politecnica de Catalunya Barcelona Spain Submitted Oct 14 2008 Accepted Apr 5 2010 Published Apr 19 2010 Mathematics Subject Classification 05C25 05C85 Abstract This paper initiates 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. Research supported by projects MEC MTM2008-05866-C03-01 and PAI P06-FQM-01649. tResearch supported by projects MEC MTM2006-01267 and DURSI 2005SGR00692. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R63 1 1 Introduction Let G be a connected graph1. A set of vertices S is a determining set of a graph G 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 of connected graphs were introduced by Boutin 4 where ways of finding and verifying determining sets are described. The author also gives natural lower bounds on the determining number of some graphs developing a complete study on Kneser graphs. Concretely tight bounds for their determining numbers are obtained and all Kneser graphs with determining number 2 3 or 4 are provided. Recently Boutin 5 has studied the determining number of Cartesian products of graphs paying special attention to powers of prime connected graphs. Moreover she computes the determining number of the .
