论文标题
总统治识别代码的界限和极端图
Bounds and extremal graphs for total dominating identifying codes
论文作者
论文摘要
图$ g $的识别代码$ c $是$ g $的统治组，因此$ g $的任何两个不同的顶点都在$ c $之内具有不同的封闭社区。 $ g $的标识代码的最小尺寸表示为$γ^{\ text {id}}}（g）$。当$ g $的每个顶点在$ c $中都有一个邻居时，据说它是$ g $的总识别代码，并且总统治$ g $的代码的最小尺寸由$γ_T^{\ text {id {id}}}（g）$表示。 扩展类似的特征以识别文献中的代码，我们对这些图表$ n $的$ g $和$γ_T^{\ text {id {id}}}（g）= n $（唯一的连接图是$ p_3 $）和$γ_t^{\ text^{\ text {id {g） $γ^{\ text {id}}}（g）= n-1 $，或通过添加一组通用顶点来从某些此类图中构建，并将其连接到其中一个私有叶子）。 然后，使用文献中的界限，我们指出，任何（开放和关闭的）订单$ n $的双二键树都具有总统治尺寸的总识别码，最多最多$ \ frac {3n} {4} $。这个绑定很紧，我们表征了到达它的树木。此外，通过一个新的证明，我们表明，这种界限实际上是至少5个无双围图的较大级别的较大级别。循环$ C_8 $也达到了这一界限。我们还为所有腰围的所有图提供了一个广义绑定，至少5个（可能与双胞胎）。 最后，我们将$γ_t^{\ text {id}}（g）$与相关参数$γ^{\ text {id}}（g）$以及$ g $的位置归因数及其变体的位置 - 势量数，提供的界限，提供的界限是紧密或紧密的。
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$. The smallest size of an identifying code of $G$ is denoted $γ^{\text{ID}}(G)$. When every vertex of $G$ also has a neighbour in $C$, it is said to be a total dominating identifying code of $G$, and the smallest size of a total dominating identifying code of $G$ is denoted by $γ_t^{\text{ID}}(G)$. Extending similar characterizations for identifying codes from the literature, we characterize those graphs $G$ of order $n$ with $γ_t^{\text{ID}}(G)=n$ (the only such connected graph is $P_3$) and $γ_t^{\text{ID}}(G)=n-1$ (such graphs either satisfy $γ^{\text{ID}}(G)=n-1$ or are built from certain such graphs by adding a set of universal vertices, to each of which a private leaf is attached). Then, using bounds from the literature, we remark that any (open and closed) twin-free tree of order $n$ has a total dominating identifying code of size at most $\frac{3n}{4}$. This bound is tight, and we characterize the trees reaching it. Moreover, by a new proof, we show that this bound actually holds for the larger class of all twin-free graphs of girth at least 5. The cycle $C_8$ also attains this bound. We also provide a generalized bound for all graphs of girth at least 5 (possibly with twins). Finally, we relate $γ_t^{\text{ID}}(G)$ to the related parameter $γ^{\text{ID}}(G)$ as well as the location-domination number of $G$ and its variants, providing bounds that are either tight or almost tight.
