论文标题
重新访问和改进上限以识别代码
Revisiting and improving upper bounds for identifying codes
论文作者
论文摘要
图$ g $的识别代码$ c $是$ g $的统治组，因此$ g $的任何两个不同的顶点都在$ c $之内具有不同的封闭社区。这些代码已被广泛研究了二十年。我们对所有最著名的上限进行了改进，其中一些已代表了20多年，用于识别树木中的代码，证明了$（n+\ ell）/2 $的上限，其中$ n $是订单，$ \ ell $是图表的叶子数（吊坠角度）。除了改善尺寸外，新的上限还可以改善一般性，因为它实际上适用于没有双胞胎（具有相同封闭或开放式邻居的顶点）2或更高程度的双分化图。我们还表明，对于无限的图形，界限很紧，并且有几个结构上不同的树木家属达到了界限。然后，我们使用自己的界限来得出$ 2N/3 $的紧密上限，用于双订单$ n $的双分两区图，并将其表征为极端示例，为$ 2 $ -Corona图形图。这是最好的，因为存在不含双图的图和带有双胞胎的树，在其任何识别代码中都需要$ n-1 $的顶点。我们还概括了$ 5N/7 $的现有上限$ n $的图形和至少没有叶子时的腰围5，而当允许叶子时，上限$ \ frac {5n+2 \ ell} {7} $。对于$ 7 $ -Cycle $ C_7 $和全明星来说，这是紧张的。
An identifying code $C$ of a graph $G$ is a dominating set of $G$ such that any two distinct vertices of $G$ have distinct closed neighbourhoods within $C$. These codes have been widely studied for over two decades. We give an improvement over all the best known upper bounds, some of which have stood for over 20 years, for identifying codes in trees, proving the upper bound of $(n+\ell)/2$, where $n$ is the order and $\ell$ is the number of leaves (pendant vertices) of the graph. In addition to being an improvement in size, the new upper bound is also an improvement in generality, as it actually holds for bipartite graphs having no twins (pairs of vertices with the same closed or open neighbourhood) of degree 2 or greater. We also show that the bound is tight for an infinite class of graphs and that there are several structurally different families of trees attaining the bound. We then use our bound to derive a tight upper bound of $2n/3$ for twin-free bipartite graphs of order $n$, and characterize the extremal examples, as $2$-corona graphs of bipartite graphs. This is best possible, as there exist twin-free graphs, and trees with twins, that need $n-1$ vertices in any of their identifying codes. We also generalize the existing upper bound of $5n/7$ for graphs of order $n$ and girth at least 5 when there are no leaves, to the upper bound $\frac{5n+2\ell}{7}$ when leaves are allowed. This is tight for the $7$-cycle $C_7$ and for all stars.
