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


Abstract:  
A set S of vertices of a digraph D is called an open neighbourhood locatingdominating
set if every vertex in D has an inneighbour in S, and for every pair u, v of vertices of D,
there is a vertex in S that is an inneighbour of exactly one of u and v. The smallest size
of an open neighbourhood locatingdominating set of a digraph D is denoted by Î³OL(D).
We study the class of digraphs D whose only open neighbourhood locatingdominating
set consists of the whole set of vertices, in other words, Î³OL(D) is equal to the order
of D. We call those digraphs extremal. By considering digraphs with loops allowed, our
definition also applies to the related (and more widely studied) concept of identifying
codes. We extend previous studies from the literature for both open neighbourhood
locatingdominating sets and identifying codes of both undirected and directed graphs.
These results all correspond to studying open neighbourhood locatingdominating sets
on special classes of digraphs. To do so, we prove general structural properties of
extremal digraphs, and we describe how they can all be constructed. We then use these
properties to give new proofs of several known results from the literature. We also give
a recursive and constructive characterization of the extremal ditrees (digraphs whose
underlying undirected graph is a tree).
Download TeX format 

back to top 