Códigos identificadores em algumas classes de grafos

Neste trabalho, investigamos o problema de se encontrar codigos identificadores de cardinalidade minima em diversas classes de grafos, tais como arvores, produtos coronas, produtos Cartesianos e prismas complementares. Para arvores caterpillar, determinamos a cardinalidade minima de um codigo identificador em caterpillars completo, grafos broom e broom duplo, e provamos um limite superior justo para caterpillars gerais. Para coronas, determinamos a cardinalidade minima de um codigo identificador em $K_n \circ \overline{K}_m$. Para produtos Cartesianos, investigamos codigos identificadores em grafos $K_{1,n} \square P_m$, definimos um limite superior justo para o caso em que $n=3$ e um limite superior mais abrangente para o caso em que $n \geq 3$. Quando $n=3$, conjecturamos que o limite proposto e minimo. Para prismas complementares de grafos, encontramos o tamanho de um codigo identificador minimo em grafos bipartidos completos e grafos split completos. Para prismas complementares, obtivemos ainda outros resultados: demonstramos que um grafo prisma complementar $G\overline{G}$ e identificavel se, e somente se, a ordem de $G$ e pelo menos dois; definimos o menor tamanho possivel de um codigo identificador em um grafo $G\overline{G}$; determinamos um limite superior justo para o codigo identificador de um grafo conexo, mostrando tambem que seu conjunto de vertices e um conjunto identificador com o tamanho proposto e, finalmente, mostramos que o grafo bipartido completo e um exemplo de grafo que atinge a igualdade do limite superior apresentado.