A1 Refereed original research article in a scientific journal
On the unicyclic graphs having vertices that belong to all their (strong) metric bases
Authors: Hakanen Anni, Junnila Ville, Laihonen Tero, Yero Ismael G
Publisher: Elsevier
Publication year: 2024
Journal: Discrete Applied Mathematics
Journal name in source: Discrete Applied Mathematics
Volume: 353
First page : 191
Last page: 207
ISSN: 0166-218X
eISSN: 1872-6771
DOI: https://doi.org/10.1016/j.dam.2024.04.020
Web address : https://doi.org/10.1016/j.dam.2024.04.020
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/393519153
A metric basis in a graph G is a smallest possible set S of vertices of G, with the property that any two vertices of G are uniquely recognized by using a vector of distances to the vertices in S. A strong metric basis is a variant of metric basis that represents a smallest possible set S′ of vertices of G such that any two vertices x,y of G are uniquely recognized by a vertex v∈S′ by using either a shortest x−v path that contains y, or a shortest y−v path that contains x. Given a graph G, there exist sometimes some vertices of G such that they forcedly belong to every metric basis or to every strong metric basis of G. Such vertices are called (resp. strong) basis forced vertices in G. It is natural to consider finding them, in order to find a (strong) metric basis in a graph. However, deciding about the existence of these vertices in arbitrary graphs is in general an NP-hard problem, which makes desirable the problem of searching for (strong) basis forced vertices in special graph classes. This article centres the attention in the class of unicyclic graphs. It is known that a unicyclic graph can have at most two basis forced vertices. In this sense, several results aimed to classify the unicyclic graphs according to the number of basis forced vertices they have are given in this work. On the other hand, with respect to the strong metric bases, it is proved in this work that unicyclic graphs can have as many strong basis forced vertices as we would require. Moreover, some characterizations of the unicyclic graphs concerning the existence or not of such vertices are given in the exposition as well.
Downloadable publication This is an electronic reprint of the original article. |  |
