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

• 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
• scientific article; zbMATH DE number 5717189 (Why is no real title available?)
• 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

(22)

• Characterizing extremal graphs for open neighbourhood location-domination
• Open locating-dominating sets in circulant graphs
• Perfect domination ratios of Archimedean lattices
• Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs
• Metric-locating-dominating sets of graphs for constructing related subsets of vertices
• Locating-dominating sets of functigraphs
• An optimal locating-dominating set in the infinite triangular grid
• Locating-domination and identification
• scientific article; zbMATH DE number 6889668 (Why is no real title available?)
• Maximum Covering Formulation for Open Locating Dominating Sets
• Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
• Extremal Digraphs for open neighbourhood location-domination and identifying codes
• Fault-tolerant locating-dominating sets on the infinite tumbling block graph
• Optimal error-detection system for identifying codes
• Open-locating dominating number for flower snarks
• On open-separating dominating codes in graphs
• Optimal error-detecting open-locating-dominating set on the infinite triangular grid
• Error-correcting open-locating-dominating sets
• Identifying open codes in trees and 4-cycle-free graphs of given maximum degree
• Fault-tolerant locating-dominating sets on the infinite king grid
• Independent location-domination number of graphs
• Fault tolerant detectors for distinguishing sets in 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)