سیویلیکا را در شبکه های اجتماعی دنبال نمایید.

On lower bounds for the metric dimension of graphs

Publish Year: 1402
Type: Journal paper
Language: English
View: 174

This Paper With 7 Page And PDF Format Ready To Download

Export:

Link to this Paper:

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 لینک شده اند :
R.C. Brigham, G. Chartrand, R.D. Dutton, and P. Zhang, On ...
G.G. Chappell, J. Gimbel, and C. Hartman, Bounds on the ...
G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Ollermann, Resolvability ...
M. Garey and D. Johnson, Computers and Intractability: A Guide ...
F. Harary and R.A. Melter, On the metric dimension of ...
B.L. Hulme, A.W. Shiver, and P.J. Slater, A Boolean algebraic ...
M.A. Johnson, Structure-activity maps for visualizing the graph variables arising ...
S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, ...
R.A. Melter, I. Tomescu, Metric bases in digital geometry, Computer ...
P.J. Slater, Leaves of trees, Congressus Numerantium ۱۴ (۱۹۷۵) ۵۴۹-۵۵۹ ...
نمایش کامل مراجع