Tese de Doutorado

Num grafo G, um conjunto de vértices C ⊆ V (G) é um código de identificação se, para cada vértice de G, a vizinhança fechada N[v] de v intersecta C, e para quaisquer vértices distintos u e v em G, temos que N[u]∩C ≠ N[v] ∩ C. Nesta tese, investigamos códigos de identificação da grade hexagonal (infinita) com k linhas, denotada por Hk. Estamos interessados em encontrar para cada k um código de identificação de Hk com a menor densidade possível, denotada por d*(Hk). Em muitas grades infinitas, é usado o método da descarga para provar limites inferiores para a densidade mínima de códigos de identificação. Não encontramos na literatura uma formalização satisfatória a respeito da aplicação desse método em grafos infinitos. Apresentamos aqui essa formalização, e mostramos que se um grafo não satisfaz certas propriedades, a aplicação do método da descarga pode levar a resultados errôneos. Usamos este método para provar que d*(Hk) ≥ 2/5 para todo k, e que d*(H2) = 9/20. Também provamos que existe um único código de identificação periódico na grade H2 com densidade 9/20. É fácil provar que d*(H1) = 1/2. Para as grades hexagonais de 3 a 5 linhas, usamos o conceito de grafo de configurações e implementamos um programa baseado neste conceito para mostrar que d*(H3) = 6/13 ≈ 0, 461538, d*(H4) = 7/16 = 0, 4375 e d*(H5) = 11/25 = 0, 44. Para as grades hexagonais com mais do que 5 linhas, mostramos que d*(H6) ≤ 47/108 ≈ 0, 43518, d*(H7p) ≤ 3/7 ≈ 0, 428571, onde p é um natural positivo, e d*(H7p+r ) ≤ 3/7 + (r/(7p + r))(d*(Hr ) - 3/7) para r ∈ [6]. Também provamos que a grade Hk é r-identificável, tem um (r, ≤ 2)-código de identificação e não tem um (r, ≤ ℓ)-código de identificação, para k ≥ 1, r ≥ 1 e ℓ ≥ 3. Estudos sobre a densidade mínima de códigos de identificação na grade hexagonal sem restrição quanto ao número de linhas (e colunas) vêm sendo realizados há mais de 20 anos, já os resultados que provamos para a grade hexagonal Hk não foram tratados antes na literatura.

In a graph G, a set of vertices C ⊆ V (G) is an identifying code if, for every vertex v of G, the closed neighborhood N[v] of v intersects C, and for any two distinct vertices u and v of G,we have N[u]∩C ≠ N[v]∩C. In this thesis we investigate identifying codes of the infinite hexagonal grid with k rows, denoted by Hk. We are interested in finding identifying codes of Hk with minimum possible density, denoted here d*(Hk). In many infinite grids, the discharging method may be used to determine lower bounds for the densities of identifying codes for such grids. However, we did not find in the literature a satisfactory formalization concerning the application of this method in infinite graphs.We present here this formalization.We also show that if a graph does not satisfy certain properties, the use of the discharging method may lead to erroneous results. We use this method to prove that d*(Hk) ≥ 2/5 for all k, and that d*(H2) = 9/20. We also prove that exists only one periodic identifying code for the grid H2 with density 9/20. It is immediate that d*(H1) = 1/2. For the hexagonal grids with 3 to 5 rows, we use the concept of configuration graph and a computer-assisted proof to show that d*(H3) = 6/13 ≈ 0.461538, d*(H4) = 7/16 = 0.4375 and d*(H5) = 11/25 = 0.44. For the hexagonal grids with more than 5 rows, we show that d*(H6) ≤ 47/108 ≈ 0.43518, d*(H7p) ≤ 3/7 ≈ 0.428571, where p is a positive natural number, and d*(H7p+r ) ≤ 3/7 + (r/(7p + r))(d*(Hr ) - 3/7), for r ∈ [6]. We also prove that the hexagonal grid Hk is r-identifiable, it has a (r, ≤ 2)-identifying code and it does not have na (r, ≤ ℓ)-identifying code, for k ≥ 1, r ≥ 1 and ℓ ≥ 3. Studies on the minimum density of identifying codes in the hexagonal grid without constraints in the number of rows (and columns) have been done for more than 20 years, however the results shown in this thesis for the hexagonal grid Hk are the first ones in the literature.