Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets

DOI10.1007/s00373-012-1136-4zbMath1267.05132arXiv1010.2985MaRDI 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

zbMATH Keywords

digraphs; identifying codes; dominating sets; infinite digraphs; induced sets

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C20: Directed graphs (digraphs), tournaments

05C63: Infinite graphs

Related Items

Extremal Digraphs for open neighbourhood location-domination and identifying codes, Identifying path covers in graphs, Set graphs. IV. Further connections with claw-freeness, On the size of identifying codes in triangle-free graphs, Domination and location in twin-free digraphs, Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code, Identifying codes in line digraphs, Set graphs. II. Complexity of set graph recognition and similar problems, Locating-Domination and Identification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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