On lower bounds for the metric dimension of graphs
Publish place: Journal of Mahani Mathematical Research، Vol: 12، Issue: 1
Publish Year: 1402
Type: Journal paper
Language: English
View: 174
This Paper With 7 Page And PDF Format Ready To Download
- Certificate
- I'm the author of the paper
Export:
Document National Code:
JR_KJMMRC-12-1_003
Index date: 1 January 2023
On lower bounds for the metric dimension of graphs abstract
For an ordered set W=\{w_1, w_2,\ldots,w_k\} of vertices and a vertex v in a connected graph G, the ordered k-vector r(v|W)=(d(v,w_1),d(v,w_2),\ldots,d(v,w_k)) is called the (metric) representation of v with respect to W, where d(x,y) is the distance between the vertices x and y. The set W is called a resolving set for G if distinct vertices of G have distinct representations with respect to W. The minimum cardinality of a resolving set for G is its metric dimension, and a resolving set of minimum cardinality is a basis of G. Lower bounds for metric dimension are important. In this paper, we investigate lower bounds for metric dimension. Motivated by a lower bound for the metric dimension k of a graph of order n with diameter d in [S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics 70(3) (1996) 217-229], which states that k \geq n-d^k, we characterize all graphs with this lower bound and obtain a new lower bound. This new bound is better than the previous one, for graphs with diameter more than 3.
On lower bounds for the metric dimension of graphs Keywords:
On lower bounds for the metric dimension of graphs authors
Mohsen Jannesari
Department of Science, Shahreza Campus, University of Isfahan, Isfahan, Iran
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :