论文标题
在具有属于其所有（强）度量基础的顶点的独一图形上
On the unicyclic graphs having vertices that belong to all their (strong) metric bases
论文作者
论文摘要
图$ g $中的度量基础是$ g $的最小的$ s $顶点的$ s $ s $，其属性是通过使用$ s $的两个距离向距离的距离向距离的距离，从而独特地识别了$ g $的任何两个顶点。强大的度量基础是公制基础的变体，它代表了$ g $的最小可能的$ s $ s $ s $ s $ s $ s $ s $ x，y $ x，y $ of $ g $的$ g $由s'$ in s'$中的s'唯一识别。鉴于图$ g $，有时存在一些$ g $的顶点，因此它们被迫属于每个度量标准或$ g $的每个强度度量。这样的顶点被称为（分别强大）$ g $的基础强制顶点。为了在图中找到（强）度量基础，可以考虑找到它们是很自然的。但是，在任意图中确定这些顶点的存在通常是一个NP-硬性问题，这使得在特殊图类类中搜索（强）强制性顶点的理想问题。本文将注意力集中在独立图的类别中。众所周知，一个单车图最多可以具有强制顶点。从这个意义上讲，在这项工作中给出了一些旨在根据其强制顶点的数量对独立图进行分类的结果。另一方面，就强大的度量基础而言，在这项工作中证明，单向图可以具有尽可能多的强大基础顶点。此外，在博览会中也给出了有关存在或不存在此类顶点的单个图形的某些特征。
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.
