Identifying codes and locating-dominating sets on paths and cycles
From MaRDI portal
Publication:642979
DOI10.1016/J.DAM.2011.06.008zbMath1228.05225arXiv0908.2750OpenAlexW2099672440MaRDI QIDQ642979
Chunxia Chen, Chang-hong Lu, Zheng-Ke Miao
Publication date: 27 October 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0908.2750
Paths and cycles (05C38) Other types of codes (94B60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (24)
LD-graphs and global location-domination in bipartite graphs ⋮ The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations ⋮ New results on variants of covering codes in Sierpiński graphs ⋮ Minimum sizes of identifying codes in graphs differing by one vertex ⋮ Optimal identifying codes of two families of Cayley graphs ⋮ Domination parameters in hypertrees and sibling trees ⋮ Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes ⋮ Sharp bound on the truncated metric dimension of trees ⋮ Locating domination in bipartite graphs and their complements ⋮ Some rainbow problems in graphs have complexity equivalent to satisfiability problems ⋮ \( [ 1 , 2 \)-dimension of graphs] ⋮ Locating-dominating codes: bounds and extremal cardinalities ⋮ Unnamed Item ⋮ The binary locating-dominating number of some convex polytopes ⋮ Identifying codes of the direct product of two cliques ⋮ Locating and identifying codes in circulant networks ⋮ Identifying codes in the direct product of a complete graph and some special graphs ⋮ Identifying codes of corona product graphs ⋮ The identifying code number and Mycielski's construction of graphs ⋮ Minimum sizes of identifying codes in graphs differing by one edge ⋮ Domination Parameters in Hypertrees ⋮ Locating-Domination and Identification ⋮ Optimal bounds on codes for location in circulant graphs ⋮ Locating-paired-dominating sets in square grids
Cites Work
- Identifying codes of cycles with odd orders
- On \(r\)-locating-dominating sets in paths
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- The minimum density of an identifying code in the king lattice.
- On the density of identifying codes in the square lattice
- Identifying and locating-dominating codes on chains and cycles
- Locating sensors in paths and cycles: the case of 2-identifying codes
- Identifying codes of cycles
- Bounds for Codes Identifying Vertices in the Hexagonal Grid
- On codes identifying vertices in the two-dimensional square lattice with diagonals
- Domination and location in acyclic graphs
- On a new class of codes for identifying vertices in graphs
- Identifying and locating-dominating codes: NP-completeness results for directed graphs
- Bounds on identifying codes
- Identifying codes with small radius in some infinite regular graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Identifying codes and locating-dominating sets on paths and cycles