Densidade mínima de códigos de identificação em grades

Abstract

In this thesis we study Identifying Code Problem in triangular grids and king grids both infinite. We denote by N[v] the closed neighborhood of v in G and, for a set C ⊆ V (G), C[v] = N[v] \ C. A set C ⊆ V (G) is an identifying code in a graph G if for all v 2 V (G), C[v] 6= ; and, for all distinct u; v 2 V (G), C[u] 6= C[v]. Let G be a graph. For any non-negative integer r, we denote by Nr(v) = x|distance(v; x) ≤ r in G. For any identifying code C ⊆ V (G), the density of C in G, denoted by d(C; G), is defined by d(C; G) = lim sup r→∞ [|C∩Nr(v0)]|/[Nr(v0)|]; where v0 is an arbitrary vertex in G. The infimum of the density of an identifying code in G is denoted by d∗(G). Given a positive integer k, let Tk be the triangular grid with k rows. Using Discharging Method, we determine the minimum density of Tk, for 2 ≤ k ≤ 6 and for odd k ≥ 7. We also determine a lower bound and a upper bound for d∗(Tk) for every even k ≥ 8 and we conjecture the exact value. We denote by Kk the king grid with k rows. Also using Discharging Method, we determine the minimum density of Kk, for 3 ≤ k ≤ 6 and we also determine a lower bound and a upper bound for d∗(Kk) for every k ≥ 7.