Identifying codes of Archimedean grids
Abstract
An identifying code of a graph is a dominating set C such that the sets N[v]∩ C are pairwise distinct. The minimum density of an identifying code has been studied extensively for several infinite grids. It is known to be 1/4 for the triangular grid and 7/20 for the square grid, whereas for the hexagonal grid the problem is still open, between 5/12 and 53/126. These three grids are the regular members of the family of the eleven Archimedean grids. In this paper, we start a systematic study of identifying codes in this family. We determine the minimum density for five of the nine Archimedean grids for which it was not known: it is 2/3 for the truncated hexagonal grid, 3/7 for the truncated square grid, and 1/3 for the trihexagonal (kagome) grid, the elongated triangular grid and the snub hexagonal grid. All lower bounds are proved by the discharging method. For the three remaining non-regular Archimedean grids, we also obtain some bounds: the minimum density lies between 3/7 and 13/30 for the truncated trihexagonal grid, between 1/3 and 11/30 for the rhombitrihexagonal grid, and between 2/7 and 9/28 for the snub square grid. As a by-product, we prove that every identifying code of a cubic graph with the slow growth property in which every vertex lies on exactly one triangle (resp. $4$-cycle) has density at least 2/3 (resp. 3/7).
Related
- On the Vertices That Belong to All Minimum Identifying Codes
- Monotonicity Property of Non-Archimedean Heat Equation
- Uniqueness of twisted linear periods over Archimedean division algebras
- The sphere is the only closed surface satisfying the fixed-width Archimedean property
- Multiplicity One Property for Archimedean Theta Correspondence
BibTeX
@misc{sampaio2026identifying,
title = {{Identifying codes of Archimedean grids}},
author = {Rudini Sampaio},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.32192},
eprint = {2610.32192},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.32192},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Identifying codes of Archimedean grids
AU - Rudini Sampaio
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.32192
UR - https://arxiv.org/abs/2610.32192
AB - An identifying code of a graph is a dominating set C such that the sets N[v]∩ C are pairwise distinct. The minimum density of an identifying code has been studied extensively for several infinite grids. It is known to be 1/4 for the triangular grid and 7/20 for the square grid, whereas for the hexagonal grid the problem is still open, between 5/12 and 53/126. These three grids are the regular members of the family of the eleven Archimedean grids. In this paper, we start a systematic study of identifying codes in this family. We determine the minimum density for five of the nine Archimedean grids for which it was not known: it is 2/3 for the truncated hexagonal grid, 3/7 for the truncated square grid, and 1/3 for the trihexagonal (kagome) grid, the elongated triangular grid and the snub hexagonal grid. All lower bounds are proved by the discharging method. For the three remaining non-regular Archimedean grids, we also obtain some bounds: the minimum density lies between 3/7 and 13/30 for the truncated trihexagonal grid, between 1/3 and 11/30 for the rhombitrihexagonal grid, and between 2/7 and 9/28 for the snub square grid. As a by-product, we prove that every identifying code of a cubic graph with the slow growth property in which every vertex lies on exactly one triangle (resp. $4$-cycle) has density at least 2/3 (resp. 3/7).
ER -