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: Graph Theory for Metric Dimension and Diameter. | Extremal Graph Theory for Metric Dimension and Diameter Carmen Hernando Departament de Matemàtica Aplicada I Universitat Politecnica de Catalunya Barcelona Spain Ignacio M. Pelayo Departament de Matematica Aplicada III Universitat Politecnica de Catalunya Barcelona Spain Merce Mora Departament de Matematica Aplicada II Universitat Politecnica de Catalunya Barcelona Spain Carlos Seara Departament de Matematica Aplicada II Universitat Politecnica de Catalunya Barcelona Spain David R. Wood Department of Mathematics and Statistics The University of Melbourne Melbourne Australia woodd@ Submitted Jul 31 2008 Accepted Feb 11 2010 Published Feb 22 2010 Subject Classification 05C12 distance in graphs 05C35 extremal graph theory Keywords graph distance resolving set metric dimension metric basis diameter order An extended abstract of this paper was presented at the European Conference on Combinatorics Graph Theory and Applications EuroComb 07 Electronic Notes in Discrete Mathematics 29 339-343 2007. Research supported by project MTM2009-07242 and Gen. Cat. DGR 2009SGR1040. Research supported by projects MTM2008-06620-C03-01 and 2009SGR-1387. Supported by a QEII Research Fellowship. Research conducted at the Univer-sitat Politecnica de Catalunya where supported by a Marie Curie Fellowship under contract MEIF-CT-2006-023865 and by projects MEC MTM2006-01267 and DURSI 2005SGR00692. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R30 1 Abstract A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. Let ỹfì D be the set of graphs with metric dimension p and diameter D. It is well-known that the minimum order of a graph in ỹp D is exactly p D. The first contribution of this paper is to characterise the graphs in ỹp D with
