Search

Abstract: An identifying code of a graph is a dominating set such that every vertex of is distinguished from other vertices by the set of vertices in that are at distance at most 1 from . 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 vertices with at least one edge admits an identifying code, then a minimal identifying code has size at most . They introduced classes of graphs whose smallest identifying code is of size . Few conjectures were formulated to classify the class of all graphs whose minimum identifying code is of size . 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. [Copyright &y& Elsevier]

The most important families of nonlinear codes are systematic. A brute-force check is the only known method to compute their weight distribution and distance distribution. On the other hand, it outputs also all closest word pairs in the code. In the black-box complexity model, the check is optimal among closest-pair algorithms. In this paper, we provide a Gröbner basis technique to compute the weight/distance distribution of any systematic nonlinear code. Also our technique outputs all closest pairs. Unlike the check, our method can be extended to work on code families. [ABSTRACT FROM AUTHOR]