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).