Choice identification of a graph
Let G G be a graph, u u be a vertex of G G , and B(u) B ( u ) (or BG(u) B G ( u ) ) be the set of u u with all its neighbors in G G . A set S S of vertices is called an identifying set  of G G if there exists a function f f from V(G) V ( G ) to the set of all nonempty subsets of S S such that (i) for each vertex u u in G G , f(u)?B(u) f ( u ) ? B ( u ) , and (ii) for every pair of distinct vertices u u and v v , f(u) f ( u ) and f(v) f ( v ) are distinct. f f is called a choice identification  of G G with respect to S S . The choice identification number ?c(G) ? c ( G ) is the cardinality of a minimum identifying set of G G . In this paper, we study the identifying sets in graphs, give a polynomial-time algorithm to find a minimum identifying set of a tree, and determine the choice identification numbers of complete bipartite graphs.
identifying set choice identification number identifying code