Códigos identificadores em algumas classes de grafos

Nenhuma Miniatura disponível

Data

2018-02-19

Título da Revista

ISSN da Revista

Título de Volume

Editor

Universidade Federal de Goiás

Resumo

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.

Descrição

Citação

FÉLIX, Juliana Paula. Códigos identificadores em algumas classes de grafos. 2018. 93 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2018.