# zbMATH — the first resource for mathematics

Neighbourhood resolving sets in graphs. II. (English) Zbl 1413.05302
Summary: P. J. Slater [Proc. 6th southeast. Conf. Comb., Graph Theor., Comput.; Boca Raton 1975, 549–559 (1975; Zbl 0316.05102)] introduced the concepts of locating sets and locating number in graphs. Subsequently with minor changes in terminology, this concept was elaborately studied by F. Harary and R. A. Melter [Ars Comb. 2 1976, No. 2, 191–195 (1976; Zbl 0349.05118)], G. Chartrand et al. [Discrete Appl. Math. 105, No. 1–3, 99–113 (2000; Zbl 0958.05042)], R. C. Brigham et al. [Math. Bohem. 128, No. 1, 25–36 (2003; Zbl 1010.05048)], G. Chartrand et al. [Math. Bohem. 128, No. 4, 379–393 (2003; Zbl 1050.05043)] and V. Saenpholphat and Ping Zhang [Int. J. Math. Math. Sci. 2004, No. 37–40, 1997–2017 (2004; Zbl 1061.05028); Czech. Math. J. 53, No. 4, 827–840 (2003; Zbl 1080.05507)]. Given an $$k$$-tuple of vectors, $$S=(v_1,v_2,\dots,v_k)$$, the neighbourhood adjacency code of a vertex $$v$$ with respect to $$S$$, denoted by $$\operatorname{nc}_S(v)$$ and defined by $$(a_1,a_2,\dots,a_k)$$ where $$a_i$$ is 1 if $$v$$ and $$v_i$$ are adjacent and 0 otherwise. $$S$$ is called a neighbourhood resolving set or a neighbourhood $$r$$-set if $$\operatorname{nc}_S(u)\neq \operatorname{nc}_S(v)$$ for any $$u,v\in V(G)$$. The least (maximum) cardinality of a minimal neighbourhood resolving set of $$G$$ is called the neighbourhood (upper neighbourhood) resolving number of $$G$$ and is denoted by $$\operatorname{nr}(G)$$ ($$\operatorname{NR}(G)$$). In this paper, bounds for $$\operatorname{nr}(G)$$,and neighbourhood resolving number for sum and composition of two graphs are obtained. neighbourhood resolving number for Mycielski graphs are discussed. Also nice results involving neighbourhood resolving numbers of $$G$$ and $$\overline G$$ are obtained.
For Part I see [the authors, “Neighbourhood resolving sets in graphs. I”, J. Math. Comput. Sci. 2, No. 4, 1012–1029 (2012)].
##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: