## “School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16723
School of Mathematics
Title:   Characterizing extremal graphs for open neighbourhood location-domination
Author(s):
 1 Narges Ghareghani 2 P Sharifani (Joint with F. Foucaud and A. Roshany-Tabrizi)
Status:   Published
Journal: Discrete Appl. Math.
Vol.:  302
Year:  2021
Pages:   76-79
Supported by:  IPM
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
scroll left or right