Identifying Code

An identifying code of a graph is a subset of its vertex set such that the sets are nonempty and pairwise distinct for all vertices , where is the closed neighborhood of (Karpovsky et al. 1998). Thus an identifying code is a dominating set with the additional requirement that different vertices have different identifying sets.

For an infinite graph, the density of an identifying code is defined by

where consists of the vertices at graph distance at most from , denotes the infimum, and denotes the limit superior (Sampaio 2026). For the infinite graphs formed by the corners and sides of five semiregular tessellations, Sampaio (2026) determined the following minimum densities. The vertex configuration records the numbers of sides of the polygons encountered cyclically around a polygon vertex.

grid	vertex configuration	minimum density
trihexagonal (kagome)
truncated hexagonal
truncated square
elongated triangular
snub hexagonal

Periodic identifying codes attain these densities (Sampaio 2026).