PaperlayerView exact revision on arXiv

Source-linked AI summary

Identifying codes of Archimedean grids

Rudini Sampaio

arXiv:2610.32192v3math.COcs.DM

TL;DR

Identifying-code minimum densities were known for only two of the eleven Archimedean grids, leaving a broad gap among the non-regular grids. The paper studies the family with periodic codes and discharging, determining five further minima and bounds for three more.

  • Problem

    Among the eight non-regular Archimedean grids, identifying codes had been considered only for the snub hexagonal grid, and minimum densities were known for only two of all eleven grids.

    Source: §1 · p. 2

  • Method

    The paper uses explicit periodic codes for upper bounds and discharging for lower bounds in its study of Archimedean grids.

    Source: §1 · p. 2

  • Results

    The paper determines minimum densities for five previously unresolved grids and gives bounds for the other three non-regular grids considered.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The discharging arguments also prove density lower bounds of 2/3 and 3/7 for cubic graphs with slow growth in which every vertex lies on exactly one triangle or exactly one 4-cycle, respectively.

    Source: §1 · p. 2

    For the rhombitrihexagonal and snub square grids, the authors expect their local discharging rules are unlikely to yield lower bounds above 1/3 and 3/10, respectively.

    Source: §8 · p. 18

Abstract

from arXiv · show

An identifying code of a graph is a dominating set $C$ such that the sets $N[v]\cap 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$).

1 Introduction

Identifying-code densities were known for only two of the eleven Archimedean grids, leaving most non-regular grids unstudied. The paper begins a systematic study, determining five more minimum densities and bounding three others.

1 Introduction

  • An identifying code is a set whose intersections with every vertex's closed neighborhood are nonempty and pairwise distinct; the concept was motivated by fault diagnosis in multiprocessor networks.Source: §1 · p. 1
  • Only two of the eleven Archimedean grids had known minimum densities; among the regular grids, the hexagonal grid remained open between 5/12 and 53/126.Source: §1 · pp. 1–2
  • Exact minimum densities are 1/3 for the trihexagonal, elongated triangular, and snub hexagonal grids, 2/3 for the truncated hexagonal grid, and 3/7 for the truncated square grid.Source: §1 · p. 2
  • The minimum density lies between 3/7 and 13/30 for the truncated trihexagonal grid, 1/3 and 11/30 for the rhombitrihexagonal grid, and 2/7 and 9/28 for the snub square grid.Source: §1 · p. 2
  • Upper bounds come from explicit periodic codes and lower bounds from discharging; the method also gives cubic-graph lower bounds of 2/3 for exactly one triangle per vertex and 3/7 for exactly one 4-cycle.Source: §1 · p. 2

2 Preliminaries

The preliminaries define Archimedean grids and identifying-code density, then establish the slow-growth setting that makes bounded-distance discharging yield density bounds.

2 Preliminaries

  • An Archimedean grid is the infinite graph of an Archimedean tiling; its vertex configuration records the cyclic polygon-side sequence around each vertex.There are eleven such tilings, and their configurations use dots and exponents for repeated polygon sizes.Source: §2 · p. 3
  • Density is the infimum over centers of the limiting upper proportion of codewords in expanding balls.For Archimedean grids, quadratic ball growth gives the slow-growth property, so density can be computed from any vertex.Source: §2 · pp. 3–4
  • Twin-free graphs admit identifying codes, and for the five grids with determined minimum density, periodic codes attain it.Twin-free means distinct vertices have distinct closed neighborhoods.Source: §2 · p. 4
  • Bounded-distance discharging preserves total charge and yields density bounds when the graph has slow growth.Starting codewords with charge 1 and others with 0, a uniform final-charge lower bound q gives density at least q; the share argument assigns each codeword at most 1 + Δ/2 total charge.Source: §2 · pp. 4–5

3 The trihexagonal grid

The trihexagonal grid, also called the kagome grid, has minimum identifying-code density 1/3, attained by an alternating pattern on horizontal lines.

3 The trihexagonal grid

  • 1/3 is the minimum identifying-code density of the trihexagonal (kagome) grid.The general lower bound for a 4-regular graph gives 1/3, and the paper constructs a code attaining it.Source: §3 · p. 5
  • The share bound is tight: each codeword contributes exactly 3 total charge in this construction.Each codeword has identifying set {c}, while every non-codeword has an identifying set of size 2.Source: §3 · p. 5
  • The code excludes middle vertices and alternates codewords with non-codewords along each horizontal line.Codewords form vertical columns; each non-codeword has a distinct identifying set, while each codeword identifies itself alone.Source: §3 · p. 5, Figure 2 · p. 6
  • There are uncountably many such density-1/3 codes, but the illustrated code is not an identifying code of the triangular grid.The triangular grid's added hexagon-center vertices duplicate the identifying set of a middle neighbor.Source: §3 · p. 6

4 The truncated hexagonal grid

The truncated hexagonal grid has minimum identifying-code density 2/3, and a general lower bound applies to cubic slow-growth graphs with exactly one triangle per vertex.

4 The truncated hexagonal grid

  • Every identifying code in a cubic slow-growth graph where each vertex lies on exactly one triangle has density at least 2/3.Each triangle requires at least two of the bridge neighbors of its vertices to be codewords; discharging sends one third of each such codeword's charge to each vertex of the adjacent triangle.Source: §4 · p. 6
  • The construction selects the two non-exit vertices in every triangle, leaving one white exit per triangle.The exit is joined by a non-vertical edge to the triangle on its left; the identifying sets distinguish the three vertices within each triangle.Source: Figure 3 · p. 7, §4 · p. 7
  • The general 2/3 bound also applies to the truncation of the 4.8.8 grid, a non-Archimedean cubic grid.In that graph, vertices lie on exactly one triangle and have configuration 3.8.16 or 3.16.16.Source: §4 · p. 7
  • 2/3 is the minimum identifying-code density of the truncated hexagonal grid.The lower bound follows from the general cubic-graph theorem, and taking every non-exit vertex gives a code of density 2/3.Source: §4 · pp. 6–7, Figure 3 · p. 7

5 The truncated square grid

The truncated square grid has minimum identifying-code density 3/7, attained by a periodic code; the lower bound extends to cubic slow-growth graphs with exactly one 4-cycle per vertex.

5 The truncated square grid

  • Every identifying code in a twin-free cubic slow-growth graph where each vertex lies on exactly one 4-cycle has density at least 3/7.The theorem applies, for example, to the truncation of any 4-regular graph.Source: §5 · p. 8
  • The lower-bound discharging scheme starts each codeword with charge 7 and redistributes charge to bridge and square neighbors.Non-codewords finish with charge 3; the case analysis ensures codewords also finish with at least 3, yielding the 3/7 density bound.Source: §5 · pp. 8–9
  • 3/7 is the minimum identifying-code density of the truncated square grid.The periodic code has 12 codewords among 28 vertices in its fundamental domain; the lower bound follows from the general theorem for cubic graphs with one 4-cycle per vertex.Source: §5 · pp. 8–9, Figure 4 · p. 9
  • The same lower-bound theorem applies to the truncation of the 3.4.6.4 grid, a non-Archimedean cubic grid.Its vertices lie on exactly one 4-cycle and have configuration 4.6.8 or 4.8.12.Source: §5 · p. 9
  • The periodic code is verified on one 28-vertex fundamental domain because vertices at distance at least 3 have disjoint closed neighborhoods.The codewords in that domain number 12, giving density 12/28 = 3/7.Source: §5 · p. 9, Figure 4 · p. 9

6 The elongated triangular grid

The elongated triangular grid has minimum identifying-code density 1/3. A discharging argument proves the lower bound by controlling charge transfers using the grid’s neighborhood structure and the identifying property.

6 The elongated triangular grid

  • Each vertex has a bridge neighbor and two outer and two inner neighbors, ordered around it as bridge, outer, inner, inner, outer.The inner neighbors are adjacent, and each outer neighbor is adjacent to one inner neighbor.Source: §6 · p. 10
  • 1/3 is the minimum identifying-code density of the elongated triangular grid.A periodic code attains the upper bound, and discharging proves the matching lower bound.Source: §6 · pp. 10, 13
  • The discharging proof starts each codeword with charge 3 and gives every vertex outside the code exactly 1 through the stated rules.Codewords may also receive 1/2; the rules distribute charge using codeword-neighbor patterns and the grid’s inner/outer structure.Source: §6 · pp. 10–11
  • To finish the lower bound, each codeword must give at most 2 plus the charge it receives, so its final charge is at least 1.The case analysis uses the fact that identifying sets must be nonempty and pairwise distinct; for example, at most one vertex in the relevant neighborhood can have identifying set {u}.Source: §6 · pp. 11–13

7 The snub hexagonal grid

The snub hexagonal grid has minimum identifying-code density 1/3. A periodic code formed from one color class of hexagons attains this density, and a local discharging case analysis proves the lower bound.

7 The snub hexagonal grid

  • 1/3 is the minimum identifying-code density of the snub hexagonal grid.The periodic code gives the upper bound, while the discharging argument establishes the matching lower bound.Source: §7 · pp. 14, 16
  • The hexagons form a triangular grid whose proper 3-coloring yields a periodic code from one color class, with density 1/3.The hexagons partition the vertices, and each contains six vertices.Source: §7 · pp. 13–14, Figure 8 · p. 15
  • For the lower bound, vertices outside the code receive total charge 1, while a local case analysis verifies that each codeword retains charge at least 1.The analysis uses neighborhoods within distance two and a table of possible codeword patterns; its rows bound outgoing charge and lower-bound received charge.Source: §7 · pp. 14–16, Table 2 · p. 16
  • The discharging rules and case analysis were developed and checked with computer help, and no fixed-priority rule among the five neighbor positions achieves the 1/3 bound.In the constructed code, identifying-set sizes 1, 2, and 3 occur in equal proportions, and every codeword ends with charge exactly 1.Source: §7 · p. 16

8 The remaining grids

The paper gives density intervals for the three remaining grids, with the truncated trihexagonal grid’s interval particularly narrow. Periodic codes found by computer search provide upper bounds, while general degree bounds or a cubic-graph result provide lower bounds.

8 The remaining grids

  • The upper bounds come from periodic codes found by constraint-solver searches over fundamental domains of about 100 to 150 vertices.For the truncated trihexagonal grid, the 3/7 lower bound follows from the cubic-graph result; the other lower bounds are the general degree bounds.Source: §8 · p. 18
  • 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.The supplied periodic-code figures show densities 13/30 for the truncated trihexagonal grid and 11/30 for the rhombitrihexagonal grid.Source: §8 · p. 18, Figure 10 · p. 19, Figure 9 · p. 19
  • The truncated trihexagonal grid’s interval is small, while the authors’ attempts suggest local N[v]∩C discharging rules are unlikely to improve the other two grids’ lower bounds beyond 1/3 and 3/10, respectively.The authors say new ideas seem needed for the rhombitrihexagonal and snub square grids.Source: §8 · p. 18
Loading 2610.32192v3…