On lower bounds for the metric dimension of graphs

سال انتشار: 1402
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 185

فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

JR_KJMMRC-12-1_003

تاریخ نمایه سازی: 11 دی 1401

چکیده مقاله:

‎For an ordered set W=\{w_۱‎, ‎w_۲,\ldots,w_k\} of vertices and a‎ vertex v in a connected graph G‎, ‎the ordered  k-vector‎ ‎r(v|W)=(d(v,w_۱),d(v,w_۲),\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‎ ‎۷۰(۳) (۱۹۹۶) ۲۱۷-۲۲۹]‎, ‎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 ۳‎.

نویسندگان

Mohsen Jannesari

Department of Science, Shahreza Campus, University of Isfahan, Isfahan, Iran

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • 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 ۱۴ (۱۹۷۵) ۵۴۹-۵۵۹ ...
  • نمایش کامل مراجع