Combinatorics and Computing Weekly Seminar
Open Neighborhood Location-domination and Identifying Codes
Open Neighborhood Location-domination and Identifying Codes
Narges Ghareghani, University of Tehran
13 DEC 2023
14:00 - 15:00
A set $ S $ of vertices of a digraph $ D $ is called an open neighborhood locating-dominating set if every vertex in $ D $ has an in-neighbor in $ S $, and for every pair $ u, v $ of vertices of $ D $, there is a vertex in $ S $ that is an in-neighbor of exactly one of $ u $ and $ v $. The smallest size of an open neighborhood locating-dominating set of a digraph $ D $ is denoted by $gamma_{OL}(D)$. We study the class of digraphs $ D $ whose only open neighborhood locating-dominating set consists of the whole set of vertices, in other words, $gamma_{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 neighborhood locating-dominating sets and identifying codes of both undirected and directed graphs. These results all correspond to studying open neighborhood locating-dominating 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 di-trees (digraphs whose underlying undirected graph is a tree).This talk is based on a common work with Florent Foucaud and Pouyeh Sharifani.
https://us06web.zoom.us/j/83407340293?pwd=cXarB4geUkQrP9MMwe8Z71K94wYPpT.1
Meeting ID : 834 0734 0293
Passcode : 362880
Venue: Niavaran, Lecture Hall 1