Extremal Digraphs for open neighbourhood location-domination and identifying codes

DOI10.1016/J.DAM.2023.12.018arXiv2302.02152MaRDI QIDQ6202938FDOQ6202938

Authors: Florent Foucaud, Narges Ghareghani, Pouyeh Sharifani 

Publication date: 27 February 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A set $S$ of vertices of a digraph $D$ is called an open neighbourhood locating dominating set if every vertex in $D$ has an in-neighbour in $S$, and for every pair $u,v$ of vertices of $D$, there is a vertex in $S$ that is an in-neighbour of exactly one of $u$ and $v$. The smallest size of an open neighbourhood locating-dominating set of a digraph $D$ is denoted by $gamm{a}_{OL}(D)$. We study the class of digraphs $D$ whose only open neighbourhood locating dominating set consists of the whole set of vertices, in other words, $gamm{a}_{OL}(D)$ is equal to the order of $D$, which we call emph{extremal}. By considering digraphs with loops allowed, our definition also applies to the related (and more widely studied) concept of identifying codes. Extending some previous studies from the literature for both open neighbourhood locating-dominating sets and identifying codes of both undirected and directed graphs (which all correspond to studying special classes of digraphs), we prove general structural properties of such 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 digraphs whose underlying undirected graph is a tree.

Full work available at URL: https://arxiv.org/abs/2302.02152

zbMATH Keywords

directed graphidentifying codelocating-dominating set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial codes (94B25)

Cites Work

• Induced subsets
• On a new class of codes for identifying vertices in graphs
• Title not available (Why is that?)
• On the minimum size of an identifying code over all orientations of a graph
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Title not available (Why is that?)
• Domination and location in acyclic graphs
• On separating systems
• Algorithmic aspects of open neighborhood location-domination in graphs
• Title not available (Why is that?)
• Dominating Set and Converse Dominating Set of a Directed Graph
• Open neighborhood locating-dominating in trees
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• A linear algorithm for minimum 1-identifying codes in oriented trees
• Bounds for identifying codes in terms of degree parameters
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• On strongly identifying codes
• Domination and location in twin-free digraphs
• Optimal open-locating-dominating sets in infinite triangular grids
• On open neighborhood locating-dominating in graphs
• Locating-dominating sets: from graphs to oriented graphs
• Discriminating codes in (bipartite) planar graphs
• Characterizing extremal graphs for open neighbourhood location-domination
• Open locating-dominating sets in circulant graphs
• Locating-dominating sets in local tournaments

This page was built for publication: Extremal Digraphs for open neighbourhood location-domination and identifying codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202938)