“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 16723 |
|
||||
| Abstract: | |||||
|
An open neighbourhood locating-dominating 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
locating-dominating set is the whole set of vertices. More precisely, we prove that these graphs are
exactly the graphs for which all connected components are half-graphs (a half-graph 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 | |||||
