부산대학교 도서관

For an ordered set W = {w1, w2, . . . , wk} of vertices in a connected graph G and a vertex v of G, the code of v with respect to W is the k-vector cW (v) = (d(v, w1), d(v, w2), . . . , d(v, wk)). The set W is an independent resolving set for G if (1) W is independent in G and (2) distinct vertices have distinct codes with respect to W. The cardinality of a minimum independent resolving set in G is the independent resolving number ir(G). We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs G of order n with ir(G) = 1, n − 1, n − 2, and present several realization results. It is shown that for every pair r, k of integers with k ≥ 2 and 0 ≤ r ≤ k, there exists a connected graph G with ir(G) = k such that exactly r vertices belong to every minimum independent resolving set of G.