← 研踪 PaperTrailarXiv:2608.24336 · v2
On the Maximum Number of Vertices that Belong to Every Metric Basis
首次提交 2026-08-25 18:00
版本更新 2026-11-19 20:01
雷达观测 2026-11-20 16:53
摘要
Resolving sets of graphs have been widely studied since their introduction in the 1970's by Slater and, independently, by Harary and Melter. The minimum cardinality of a resolving set of a graph is called the metric dimension of and is denoted by . In this paper, we concentrate on the existence of vertices in a graph that belong to all metric bases of , i.e. resolving sets of cardinality . Such vertices are called basis forced vertices, and we denote the number of them by . We show that for any connected nontrivial graph of order . In addition, we show that this bound can be attained. Furthermore, it also implies that holds for any nontrivial connected graph . This result answers a question posed by Bagheri \emph{et al.} in 2016. Moreover, we provide a complete realization of the parameters , and within the previous bounds. We consider some extremal cases related to basis forced vertices in a graph, in particular, we give a full characterization of the graphs with and .
作者备注:20 pages, 8 figures. Parts of this paper appeared in CALDAM 2025
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-19 20:01 · 最新观测版本
On the Maximum Number of Vertices that Belong to Every Metric Basis
Resolving sets of graphs have been widely studied since their introduction in the 1970's by Slater and, independently, by Harary and Melter. The minimum cardinality of a resolving set of a graph is called the metric dimension of and is denoted by . In this paper, we concentrate on the existence of vertices in a graph that belong to all metric bases of , i.e. resolving sets of cardinality . Such vertices are called basis forced vertices, and we denote the number of them by . We show that for any connected nontrivial graph of order . In addition, we show that this bound can be attained. Furthermore, it also implies that holds for any nontrivial connected graph . This result answers a question posed by Bagheri \emph{et al.} in 2016. Moreover, we provide a complete realization of the parameters , and within the previous bounds. We consider some extremal cases related to basis forced vertices in a graph, in particular, we give a full characterization of the graphs with and .
查看此版本解读 →查看此版本原文 ↗