On the unicyclic graphs having vertices that belong to all their (strong) metric bases
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912570534789120 |
|---|---|
| author | Hakanen, Anni Junnila, Ville Laihonen, Tero Yero, Ismael G. |
| author_facet | Hakanen, Anni Junnila, Ville Laihonen, Tero Yero, Ismael G. |
| contents | 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\in 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 centers 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_02311 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the unicyclic graphs having vertices that belong to all their (strong) metric bases Hakanen, Anni Junnila, Ville Laihonen, Tero Yero, Ismael G. Combinatorics 05C12 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\in 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 centers 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. |
| title | On the unicyclic graphs having vertices that belong to all their (strong) metric bases |
| topic | Combinatorics 05C12 |
| url | https://arxiv.org/abs/2209.02311 |