On lower bounds for the metric dimension of graphs
- سال انتشار: 1402
- محل انتشار: دوفصلنامه مرکز پژوهشی ریاضی ماهانی، دوره: 12، شماره: 1
- کد COI اختصاصی: JR_KJMMRC-12-1_003
- زبان مقاله: انگلیسی
- تعداد مشاهده: 105
نویسندگان
Department of Science, Shahreza Campus, University of Isfahan, Isfahan, Iran
چکیده
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 ۳.کلیدواژه ها
Resolving set, Metric dimension, Metric basis, Lower bound, Diameterاطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.