Códigos identificadores em algumas classes de grafos

• Ano de defesa: 2018
• Autor(a) principal: Félix, Juliana Paula
• Orientador(a): Santana, Márcia Rodrigues Cappelle
• Banca de defesa: Santana, Márcia Rodrigues Cappelle, Castonguay, Diane, Souza, Uéverton dos Santos
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: Códigos identificadores; Caterpillar; Produto corona; Produto cartesiano; Prisma complementar
• Palavras-chave em Inglês: Identifying codes; Caterpillar; Corona product; Cartesian product; Complementary prism
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/8222

In this work, we investigate the problem of finding identifying codes of minimum size in a variety of graph classes, such as trees corona products, Cartesian products and complementary prisms. For caterpillar trees, we show the minimum size of an identifying code on complete caterpillars, brooms and double brooms. We also prove a sharp upper bound for the general case. For coronas $K_n \circ \overline{K}_m$, we prove what is the minimum size of an identifying code. We demonstrate a sharp upper bound for an identifying code of the Cartesian product of a star and a path $K_{1,n} \square P_m$ and, when $n=3$, we conjecture that the limit proposed is minimum. We also find the minimum cardinality of an identifying code in the complementary prism of complete bipartite graphs and complete split graphs, among with other results: we demonstrate that the complementary prism graph $G\overline{G}$ is identifiable if, and only if, $G$ has at least two vertices; we find what is the smallest size possible of an identifying code of complementary prisms; we prove a sharp upper bound for an identifying code of the complementary prism $G\overline{G}$ of a connected graph $G$, showing that the set $C = V(G)$ is an identifying code with the size proposed and, finally, we determine the size of a minimum identifying code of the complementary prism of a complete bipartite graph, showing that it is an example of a graph that attains our upper bound.