آمار
| تعداد نشریات | 26 |
| تعداد شماره‌ها | 447 |
| تعداد مقالات | 4,557 |
| تعداد مشاهده مقاله | 5,380,001 |
| تعداد دریافت فایل اصل مقاله | 3,580,066 |
On lower bounds for the metric dimension of graphs | ||
| Journal of Mahani Mathematical Research | ||
| دوره 12، شماره 1 - شماره پیاپی 24، فروردین 2023، صفحه 35-41 اصل مقاله (492.59 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22103/jmmrc.2022.19121.1211 | ||
| نویسنده | ||
| Mohsen Jannesari* | ||
| Department of Science, Shahreza Campus, University of Isfahan, Isfahan, Iran | ||
| چکیده | ||
| 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$. | ||
| کلیدواژه‌ها | ||
| Resolving set؛ Metric dimension؛ Metric basis؛ Lower bound؛ Diameter | ||
| مراجع | ||
|
[1] R.C. Brigham, G. Chartrand, R.D. Dutton, and P. Zhang, On the dimension of trees, Discrete Mathematics 294 (2005) 279-283.
[2] G.G. Chappell, J. Gimbel, and C. Hartman, Bounds on the metric and partition dimensions of a graph, Ars Combinatoria 88 (2008) 349-366.
[3] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Ollermann, Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics 105 (2000) 99-113.
[4] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NO-Completeness, Freeman, New York, 1979.
[5] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combinatoria 2 (1976) 191-195.
[6] B.L. Hulme, A.W. Shiver, and P.J. Slater, A Boolean algebraic analysis of re protection, Algebraic and Combinatorial Methods in Operations Research, 95 (1984) 215-227.
[7] M.A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, Journal of Biopharmaceutical Statistics 3 (1993) 217-229.
[8] S. Khuller, B. Raghavachari, and A. Rosenfeld, Landmarks in graphs, Discrete Applied Mathematics 70(3) (1996) 217-229.
[9] R.A. Melter, I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25 (1984), 113-121.
[10] P.J. Slater, Leaves of trees, Congressus Numerantium 14 (1975) 549-559. | ||
|
آمار تعداد مشاهده مقاله: 433 تعداد دریافت فایل اصل مقاله: 1,026 |
||