Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
From MaRDI portal
Publication:2376092
DOI10.1007/s00373-012-1136-4zbMath1267.05132arXiv1010.2985OpenAlexW3101195735MaRDI QIDQ2376092
Reza Naserasr, Aline Parreau, Florent Foucaud
Publication date: 26 June 2013
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.2985
Structural characterization of families of graphs (05C75) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63)
Related Items (9)
Identifying path covers in graphs ⋮ Set graphs. IV. Further connections with claw-freeness ⋮ Identifying codes in line digraphs ⋮ Extremal Digraphs for open neighbourhood location-domination and identifying codes ⋮ On the size of identifying codes in triangle-free graphs ⋮ Set graphs. II. Complexity of set graph recognition and similar problems ⋮ Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code ⋮ Locating-Domination and Identification ⋮ Domination and location in twin-free digraphs
Cites Work
- Extremal cardinalities for identifying and locating-dominating codes in graphs
- On graphs having a \(V\setminus \{x\}\) set as an identifying code
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Another algebraic proof of Bondy's theorem on induced subsets
- Extremal graphs for the identifying code problem
- A linear algorithm for minimum 1-identifying codes in oriented trees
- Induced subsets
- On a new class of codes for identifying vertices in graphs
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets
