Characterizing Extremal Digraphs for Identifying Codes and Extremal Cases of Bondy’s Theorem on Induced Subsets
Characterizing Extremal Digraphs for Identifying Codes and Extremal Cases of Bondy’s Theorem on Induced Subsets
复制标题
表征极值有向图以识别邦迪诱导子集定理的代码和极值情况
DOI：
10.1007/s00373-012-1136-4
复制
发表时间：
2010
影响因子：
0.7
通讯作者：
Aline Parreau
中科院分区：
文献类型：
--
作者：
Florent Foucaud;R. Naserasr;Aline Parreau
(Di)图G的一个识别码是G的顶点的一个控制子集C，使得G的所有不同的顶点在C内都有不同的(In)邻域。本文将所有只接受其整个顶点集的有限有向图归类为一个识别码。我们还对所有这样的无限定向图进行了分类。此外，通过将这一概念与集合系上著名的Bondy定理联系起来，我们对该定理的极值情况进行了分类。
An identifying code of a (di)graph G is a dominating subset C of the vertices of G such that all distinct vertices of G have distinct (in)neighbourhoods within C. In this paper, we classify all finite digraphs which only admit their whole vertex set as an identifying code. We also classify all such infinite oriented graphs. Furthermore, by relating this concept to a well-known theorem of Bondy on set systems, we classify the extremal cases for this theorem.