O número de Carathéodory na convexidade geodésica de grafos

• Ano de defesa: 2016
• Autor(a) principal: Lira, Eduardo Silva
• Orientador(a): Coelho, Erika Morais Martins
• Banca de defesa: Coelho, Erika Morais Martins, Castonguay, Diane, Santana, Márcia Rodrigues Cappelle, Szwarcfiter, Jayme Luiz
• 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: Grafos; Número de Carathéodory; Convexidade geodésica; Produto cartesiano; Prisma complementar
• Palavras-chave em Inglês: Graph; Carathéodory number; Geodesic convexity; 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/6673

From Carathéodory’s theorem arises the definition of the Carathéodory number for graphs. This number is well-known for monophonic and triangle-path convexities. It is limited for some classes of graphs on P3 and geodesic convexities but is known to be unlimited only on P3-convexity. Driven by open questions in geodesic convexity, in this work we study the Carathéodory number in this convexity. For general graphs and cartesian product, we prove that the Carathéodory number is unlimited. We characterize the Carathéodory number for trees, cographs, for the complementary prisms of cographs and simple graphs Kn, Pn and Cn, for the complement and the complementary prism of the graph KnKn and for the cartesian products PnxPm, KnxKm and PnxKm.