“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 16723  


Abstract:  
An open neighbourhood locatingdominating set is a set S of vertices of a graph G such that each
vertex of G has a neighbour in S, and for any two vertices u, v of G, there is at least one vertex in S that
is a neighbour of exactly one of u and v. We characterize those graphs whose only open neighbourhood
locatingdominating set is the whole set of vertices. More precisely, we prove that these graphs are
exactly the graphs for which all connected components are halfgraphs (a halfgraph is a special bipartite
graph with both parts of the same size, where each part can be ordered so that the open neighbourhoods
of consecutive vertices differ by exactly one vertex). This corrects a wrong characterization from the
literature.
Download TeX format 

back to top 