Metric bases of graphs have been widely studied since their introduction in the 1970’s by Slater and, independently, by Harary and Melter. In this paper, we concentrate on the existence of vertices in a graph G that belong to all metric bases of G. We call these basis forced vertices, and denote the number of them by \(\textrm{bf}(G)\) . We show that \(\textrm{bf}(G)\le 2/3(n-k-1)\) for any connected nontrivial graph G of order n having k vertices in each metric basis. In addition, we show that this bound can be attained. Furthermore, the previous result implies the bound \(\textrm{bf}(G)\le 2/5(n-1)\) formulated in terms of the order n of the graph for any nontrivial connected graph G. This result answers a question posed by Bagheri et al. in 2016. Moreover, we provide some realization results and consider some extremal cases related to basis forced vertices in a graph.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On a Tight Bound for the Maximum Number of Vertices that Belong to Every Metric Basis

  • Anni Hakanen,
  • Ville Junnila,
  • Tero Laihonen,
  • Havu Miikonen,
  • Ismael G. Yero

摘要

Metric bases of graphs have been widely studied since their introduction in the 1970’s by Slater and, independently, by Harary and Melter. In this paper, we concentrate on the existence of vertices in a graph G that belong to all metric bases of G. We call these basis forced vertices, and denote the number of them by \(\textrm{bf}(G)\) . We show that \(\textrm{bf}(G)\le 2/3(n-k-1)\) for any connected nontrivial graph G of order n having k vertices in each metric basis. In addition, we show that this bound can be attained. Furthermore, the previous result implies the bound \(\textrm{bf}(G)\le 2/5(n-1)\) formulated in terms of the order n of the graph for any nontrivial connected graph G. This result answers a question posed by Bagheri et al. in 2016. Moreover, we provide some realization results and consider some extremal cases related to basis forced vertices in a graph.