Identifying codes and locating-dominating sets on paths and cycles

DOI10.1016/J.DAM.2011.06.008zbMATH Open1228.05225arXiv0908.2750OpenAlexW2099672440MaRDI QIDQ642979FDOQ642979

Authors: Chunxia Chen, Changhong Lu, Zhengke Miao 

Publication date: 27 October 2011

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

Abstract: Let $G=(V,E)$ be a graph and let $rge1$ be an integer. For a set $DsubseteqV$, define $N_r[x]=yinV:d(x,y)leqr$ and $D_r(x)=N_r[x]capD$, where $d(x,y)$ denotes the number of edges in any shortest path between $x$ and $y$. $D$ is known as an $r$-identifying code ($r$-locating-dominating set, respectively), if for all vertices $xinV$ ($$, respectively), $D_r(x)$ are all nonempty and different. In this paper, we provide complete results for $r$-identifying codes in paths and odd cycles; we also give complete results for 2-locating-dominating sets in cycles.

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

Recommendations

• Identifying and locating-dominating codes on chains and cycles
• Locating sensors in paths and cycles: the case of 2-identifying codes
• Extremal cardinalities for identifying and locating-dominating codes in graphs
• On \(r\)-locating-dominating sets in paths
• Locating-dominating codes in cycles

zbMATH Keywords

pathscycles\(r\)-identifying codes\(r\)-locating-dominating sets

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38) Other types of codes (94B60)

Cites Work

• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On identifying codes
• On a new class of codes for identifying vertices in graphs
• Identifying and locating-dominating codes on chains and cycles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Domination and location in acyclic graphs
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Title not available (Why is that?)
• Identifying codes of cycles
• Title not available (Why is that?)
• Bounds for codes identifying vertices in the hexagonal grid
• The minimum density of an identifying code in the king lattice.
• On codes identifying vertices in the two-dimensional square lattice with diagonals
• Bounds on identifying codes
• Identifying codes with small radius in some infinite regular graphs
• On the density of identifying codes in the square lattice
• Title not available (Why is that?)
• On \(r\)-locating-dominating sets in paths
• Locating sensors in paths and cycles: the case of 2-identifying codes
• Locating-dominating codes in cycles
• Identifying codes of cycles with odd orders

Cited In (33)

• The identifying code number and Mycielski's construction of graphs
• New results on variants of covering codes in Sierpiński graphs
• Locating sensors in paths and cycles: the case of 2-identifying codes
• Title not available (Why is that?)
• LD-graphs and global location-domination in bipartite graphs
• Locating vertices using codes
• Locating-paired-dominating sets in square grids
• \( [ 1 , 2 ]\)-dimension of graphs
• Solving Two Conjectures regarding Codes for Location in Circulant Graphs
• Locating-dominating codes: bounds and extremal cardinalities
• Optimal bounds on codes for location in circulant graphs
• Domination Parameters in Hypertrees
• Locating domination in bipartite graphs and their complements
• Sharp bound on the truncated metric dimension of trees
• Some rainbow problems in graphs have complexity equivalent to satisfiability problems
• Identifying and locating-dominating codes on chains and cycles
• Identifying codes in the direct product of a complete graph and some special graphs
• The identifying code, the locating-dominating, the open locating-dominating and the locating total-dominating problems under some graph operations
• Minimum sizes of identifying codes in graphs differing by one edge
• Identifying codes of the direct product of two cliques
• Identifying codes of corona product graphs
• Locating-Domination and Identification
• Optimal identifying codes of two families of Cayley graphs
• Identifying codes of cycles
• Domination parameters in hypertrees and sibling trees
• Locating and identifying codes in circulant networks
• Minimum sizes of identifying codes in graphs differing by one vertex
• Identifying codes of cycles with odd orders
• Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes
• On \(r\)-locating-dominating sets in paths
• The binary locating-dominating number of some convex polytopes
• Locating-dominating codes in paths
• Locating-dominating codes in cycles

This page was built for publication: Identifying codes and locating-dominating sets on paths and cycles

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