Extremal Digraphs for open neighbourhood location-domination and identifying codes

DOI10.1016/J.DAM.2023.12.018MaRDI QIDQ6202938zbMATH OpenFDO

Authors Florent Foucaud, Narges Ghareghani, Pouyeh Sharifani

Publication date 27 February 2024

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

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)

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.

Recommendations

• Characterizing extremal graphs for open neighbourhood location-domination
• Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
• Domination and location in twin-free digraphs
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Locating-dominating sets in local tournaments

Cites work

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

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)