Minimum identifying codes in some graphs differing by matchings

摘要

For a vertex v of a graph G, let N-G[v] be the set of v with all of its neighbors in G. A set C of vertices is an identifying code of C if the sets NG[v] boolean AND C are nonempty and distinct for all vertices v of G. If G admits an identifying code, then G is called identifiable and the minimum cardinality of an identifying code of G is denoted by i(G). Let m, n be two positive integers. In this paper, i((C-n) over bar) and i((P-n) over bar) are computed, where (P-n) over bar and (C-n) over bar represent the complement of a path and the complement of a cycle of order n, respectively. Among other results, i(K-m,K-n*) is given, where K-m,K-n* is obtained from K-m,K-n after deleting a maximum matching.