A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
On a Tight Bound for the Maximum Number of Vertices that Belong to Every Metric Basis
Tekijät: Hakanen, Anni; Junnila, Ville; Laihonen, Tero; Miikonen, Havu; Yero, Ismael G.
Toimittaja: Gaur, Daya; Mathew, Rogers
Konferenssin vakiintunut nimi: Conference on Algorithms and Discrete Applied Mathematics
Kustantaja: Springer Nature Switzerland
Julkaisuvuosi: 2025
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Algorithms and Discrete Applied Mathematics: 11th International Conference, CALDAM 2025, Coimbatore, India, February 13–15, 2025, Proceedings
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta: 15536
Aloitussivu: 173
Lopetussivu: 184
ISBN: 978-3-031-83437-0
eISBN: 978-3-031-83438-7
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-031-83438-7_15
Verkko-osoite: https://doi.org/10.1007/978-3-031-83438-7_15
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/491723438
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 bf(G). We show that bf(G)≤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 bf(G)≤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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Julkaisussa olevat rahoitustiedot:
Ismael G. Yero has been partially supported by the Spanish Ministry of Science and Innovation through the grant PID2023-146643NB-I00. Ville Junnila, Tero Laihonen and Havu Miikonen have been partially supported by Academy of Finland grant number 338797. Anni Hakanen was supported by Turku Collegium for Science, Medicine and Technology (TCSMT).
