Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-16T10:48:35Z
No. of bitstreams: 2
Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-16T10:49:04Z (GMT) No. of bitstreams: 2
Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-16T10:49:04Z (GMT). No. of bitstreams: 2
Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2018-02-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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. / Neste trabalho, investigamos o problema de se encontrar códigos identificadores de cardinalidade
mínima em diversas classes de grafos, tais como árvores, produtos coronas, produtos Cartesianos e
prismas complementares. Para árvores caterpillar, determinamos a cardinalidade mínima de um
código identificador em caterpillars completo, grafos broom e broom duplo, e provamos um limite
superior justo para caterpillars gerais. Para coronas, determinamos a cardinalidade mínima de um
código identificador em $K_n \circ \overline{K}_m$. Para produtos Cartesianos, investigamos
códigos 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 é mínimo. Para prismas complementares de grafos,
encontramos o tamanho de um código identificador mínimo em grafos bipartidos completos e
grafos split completos. Para prismas complementares, obtivemos ainda outros resultados:
demonstramos que um grafo prisma complementar $G\overline{G}$ é identificável se, e somente
se, a ordem de $G$ é pelo menos dois; definimos o menor tamanho possível de um código
identificador em um grafo $G\overline{G}$; determinamos um limite superior justo para o código
identificador de um grafo conexo, mostrando também que seu conjunto de vértices é um conjunto
identificador com o tamanho proposto e, finalmente, mostramos que o grafo bipartido completo é
um exemplo de grafo que atinge a igualdade do limite superior apresentado.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/8222 |
| Date | 19 February 2018 |
| Creators | Félix, Juliana Paula |
| Contributors | Santana, Márcia Rodrigues Cappelle, Santana, Márcia Rodrigues Cappelle, Castonguay, Diane, Souza, Uéverton dos Santos |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, 2075167498588264571 |
Page generated in 0.0029 seconds