Watching systems in graphs: an extension of identifying codes

DOI10.1016/j.dam.2011.04.025zbMath1287.05142arXiv1005.0765OpenAlexW1551710741MaRDI QIDQ2446294

Olivier Hudry, David Auger, Irène Charon, Antoine C. Lobstein

Publication date: 16 April 2014

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

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

zbMATH Keywords

complexitypathscyclesidentifying codeswatching systems

Mathematics Subject Classification ID

Paths and cycles (05C38) Other types of codes (94B60) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Watching systems in the King grid ⋮ Extremal cubic graphs for fault-tolerant locating domination ⋮ On the watching number of graphs using discharging procedure ⋮ The watching system as a generalization of identifying code ⋮ Identifying path covers in graphs ⋮ On redundant locating-dominating sets ⋮ Identifying codes and watching systems in Kneser graphs ⋮ Choice identification of a graph ⋮ Unnamed Item ⋮ Optimal \((r,\leq 3)\)-locating-dominating codes in the infinite king grid ⋮ Maximum size of a minimum watching system and the graphs achieving the bound ⋮ Locating-Domination and Identification ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum size of a minimum watching system and the graphs achieving the bound
• Constructing codes identifying sets of vertices
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• On graphs having a \(V\setminus \{x\}\) set as an identifying code
• Codes identifying sets of vertices in random networks
• Discriminating codes in (bipartite) planar graphs
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
• On the identification problems in products of cycles
• On the identification of vertices using cycles
• Identifying and locating-dominating codes on chains and cycles
• Complexity results for identifying codes in planar graphs
• Discriminating codes in bipartite graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On a new class of codes for identifying vertices in graphs
• Reducibility among Combinatorial Problems
• Nonrandom binary superimposed codes
• Links Between Discriminating and Identifying Codes in the Binary Hamming Space