Códigos identificadores em algumas classes de grafos
Nenhuma Miniatura disponível
Data
2018-02-19
Autores
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
Palavras-chave
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.