On the Maximum Number of Vertices that Belong to Every Metric Basis
Anni Hakanen, Ville Junnila, Tero Laihonen, Havu Miikonen, Ismael G. Yero
原文摘要
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 $G$ is called the metric dimension of $G$ and is denoted by $\dim(G)$. In this paper, we concentrate on the existence of vertices in a graph $G$ that belong to all metric bases of $G$, i.e. resolving sets of cardinality $\dim(G)$. Such vertices are called basis forced vertices, and we denote the number of them by $\mathrm{bf}(G)$. We show that $\mathrm{bf}(G)\le 2/3(n-\dim(G)-1)$ for any connected nontrivial graph $G$ of order $n$. In addition, we show that this bound can be attained. Furthermore, it also implies that $\mathrm{bf}(G)\le 2/5(n-1)$ holds for any nontrivial connected graph $G$. This result answers a question posed by Bagheri \emph{et al.} in 2016. Moreover, we provide a complete realization of the parameters $n$, $\dim(G)$ and $\mathrm{bf}(G) \ge 1$ 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 $\mathrm{bf}(G) = 2$ and $\dim(G) = n-4$.
math.CO · cs.DM