Extremal graphs for the identifying code problem
Extremal graphs for the identifying code problem
复制标题
识别码问题的极值图
DOI：
10.1016/j.ejc.2011.01.002
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Petru Valicov
中科院分区：
文献类型：
--
作者：
Florent Foucaud;Eleonora Guerrini;M. Kovse;R. Naserasr;Aline Parreau;Petru Valicov
图G的一个识别码是一个支配集C，使得G的每个顶点x都是由C中距x至多1的顶点集来区分的，寻找一个最小可能大小的识别码是一个具有挑战性的问题。N.Bertrand，I.Charon，O.Hudry和A.Lobstein证明了：如果一个至少有一条边的n个顶点上的图允许一个识别码，则一个最小识别码的大小至多为n−1.他们引入了一类最小识别码为n−1的图.几乎没有人提出猜想来分类所有最小识别码为n−1的图.本文驳斥了这些猜想，我们对除一个顶点外的所有顶点都需要构成一个识别码的所有有限图进行分类.我们将所有需要全部顶点集的无限图归类到任意一个识别码中。文中还给出了图的顶点数和最大度的新的上界。
An identifying code of a graph G is a dominating set C such that every vertex x of G is distinguished from other vertices by the set of vertices in C that are at distance at most 1 from x. The problem of finding an identifying code of minimum possible size turned out to be a challenging problem. It was proved by N. Bertrand, I. Charon, O. Hudry and A. Lobstein that if a graph on n vertices with at least one edge admits an identifying code, then a minimal identifying code has size at most n−1. They introduced classes of graphs whose smallest identifying code is of size n−1. Few conjectures were formulated to classify the class of all graphs whose minimum identifying code is of size n−1. In this paper, disproving these conjectures, we classify all finite graphs for which all but one of the vertices are needed to form an identifying code. We classify all infinite graphs needing the whole set of vertices in any identifying code. New upper bounds in terms of the number of vertices and the maximum degree of a graph are also provided.