Optimal open-locating-dominating sets in infinite triangular grids

DOI10.1016/J.DAM.2015.04.024MaRDI QIDQ2354721zbMATH OpenOpenAlexFDO

Authors Rex K. Kincaid, Allison Oldham, Gexin Yu

Publication date 24 July 2015

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

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

zbMATH Keywords

infinite triangular gridopen-locating-domination set

Mathematics Subject Classification ID

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

Abstract: An open-locating-dominating set (OLD-set) is a subset of vertices of a graph such that every vertex in the graph has at least one neighbor in the set and no two vertices in the graph have the same set of neighbors in the set. This is an analogue to the well-studied identifying code in the literature. In this paper, we prove that the optimal density of the OLD-set for the infinite triangular grid is $4/13$.

Recommendations

• An optimal locating-dominating set in the infinite triangular grid
• scientific article; zbMATH DE number 6889668
• scientific article; zbMATH DE number 5717189
• On open neighborhood locating-dominating in graphs
• Open neighborhood locating-domination for grid-like graphs

Cites work

• scientific article; zbMATH DE number 5717189 (Why is no real title available?)
• A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
• An optimal edge-robust identifying code in the triangular lattice
• An optimal locating-dominating set in the infinite triangular grid
• An optimal strongly identifying code in the infinite triangular grid
• Bounds for codes identifying vertices in the hexagonal grid
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Lower bounds for identifying codes in some infinite grids
• New bounds on the minimum density of an identifying code for the infinite hexagonal grid
• On a new class of codes for identifying vertices in graphs
• On strongly identifying codes
• Open neighborhood locating-dominating in trees

Cited in

(15)

• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• scientific article; zbMATH DE number 6889668 (Why is no real title available?)
• Locating-domination and identification
• An optimal locating-dominating set in the infinite triangular grid
• Characterizing extremal graphs for open neighbourhood location-domination
• Fault tolerant detectors for distinguishing sets in graphs
• Perfect domination ratios of Archimedean lattices
• Open locating-dominating sets in circulant graphs
• Maximum Covering Formulation for Open Locating Dominating Sets
• Fault-tolerant locating-dominating sets on the infinite tumbling block graph
• Extremal Digraphs for open neighbourhood location-domination and identifying codes
• Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
• Locating-dominating sets of functigraphs
• Optimal error-detection system for identifying codes
• Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs

This page was built for publication: Optimal open-locating-dominating sets in infinite triangular grids

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