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

DOI10.1007/S00373-012-1136-4MaRDI QIDQ2376092zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Reza Naserasr, Aline Parreau

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

digraphsdominating setsidentifying codesinduced setsinfinite digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: An identifying code of a (di)graph $G$ is a dominating subset $C$ of the vertices of $G$ such that all distinct vertices of $G$ have distinct (in)neighbourhoods within $C$. In this paper, we classify all finite digraphs which only admit their whole vertex set in any identifying code. We also classify all such infinite oriented graphs. Furthermore, by relating this concept to a well known theorem of A. Bondy on set systems we classify the extremal cases for this theorem.

Recommendations

• Extremal graphs for the identifying code problem
• Identifying codes in line digraphs
• Characterizing identifying codes from the spectrum of a graph or digraph
• Sufficient conditions for a digraph to admit a (1, )-identifying code
• Extremal cardinalities for identifying and locating-dominating codes in graphs

Cites work

• A linear algorithm for minimum 1-identifying codes in oriented trees
• Another algebraic proof of Bondy's theorem on induced subsets
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• Extremal graphs for the identifying code problem
• scientific article; zbMATH DE number 3906528 (Why is no real title available?)
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Induced subsets
• On a new class of codes for identifying vertices in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code

Cited in

(12)

• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Sufficient conditions for a digraph to admit a (1, )-identifying code
• Identifying codes in line digraphs
• Set graphs. II. Complexity of set graph recognition and similar problems
• Extremal graphs for the identifying code problem
• Locating-domination and identification
• Identifying path covers in graphs
• Set graphs. IV. Further connections with claw-freeness
• On the size of identifying codes in triangle-free graphs
• Extremal Digraphs for open neighbourhood location-domination and identifying codes
• On identifying vertices of tournament digraphs
• Domination and location in twin-free digraphs

This page was built for publication: Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets

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