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)].
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Full Text: Link