Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/10191
Type: Tese
Title: Diâmetro de grafos fulerenes e transversalidade de ciclos ímpares de fuleróides-(3, 4, 5, 6)
Author(s)/Inventor(s): Nicodemos, Diego de Souza
Advisor: Klein, Sulamita
Co-advisor: Faria, Luerbio
Co-advisor: Stehlík, Matěj
Abstract: Os grafos fulerenes são modelos matemáticos para moléculas compostas exclusivamente por átomos de carbono, descobertas experimentalmente no início da década de 80 por Kroto, Heath, O’Brien, Curl e Smalley. Muitos parâmetros associados a estes grafos vêm sendo discutidos, buscando descrever a estabilidade das moléculas de fulerene. Precisamente falando, grafos fulerenes são grafos cúbicos, planares, 3-conexos cujas faces são pentagonais e hexagonais. A Conjectura de Andova e Škrekovski [1] afirma que o diâmetro de todo grafo fulerene, contendo n vértices, é pelo menos igual a jq 5n 3 k − 1. Esta conjectura tornou-se relevante, pois Andova e Škrekovski conceberam-na a partir do estudo de grafos fulerenes altamente regulares, esféricos e simétricos. Introduzimos os conceitos de curvatura combinatória de vértice e curvatura combinatória de face de um grafo planar. Definimos, então, uma classe particular de grafos fulerenes, chamada de nanodiscos de fulerene. Mostramos que a Conjectura de Andova e Škrekovski não é válida para nenhum nanodisco de fulerene com mais de 300 vértices. No entanto, exibimos infinitas classes de grafos fulerenes, semelhantes aos grafos estudados por Andova e Škrekovski, que satisfazem a referida conjectura. Acrescentando, aos grafos fulerenes, faces triangulares e quadrangulares concebemos os grafos fuleróides-(3, 4, 5, 6). Estudamos os problemas da frustração bipartida de arestas e do conjunto independente máximo sobre os grafos fuleróides-(3, 4, 5, 6), obtendo limites apertados para ambos os problemas.
Abstract: Fullerene graphs are mathematical models for molecules composed exclusively of carbon atoms, discovered experimentally in the early 1980s by Kroto, Heath, O’Brien, Curl and Smalley. Many parameters associated to these graphs have been discussed, trying to describe the stability of the fullerene’s molecule. Formally, fulerene graphs are 3-connected, cubic, planar graphs with pentagonal and hexagonal faces. Andova and Škrekovski Conjecture [1] states that the diameter of all fullerene graph, on n vertices, is at least equal to jq 5n 3 k −1. This conjecture became relevant, since Andova and Škrekovski conceived it from the study of highly regular, spherical and symmetrical fullerene graphs. We introduce the concepts of combinatorial curvature of vertex and combinatorial curvature of face of a planar graph and then we define a specific class of fullerene graphs, called fullerene nanodiscs. We have shown that the Andova and Škrekovski Conjecture is not valid for any fullerene nanodisc with more than 300 vertices. However, we exhibit infinite classes of fullerene graphs, similar to the graphs studied by Andova and Škrekovski, which satisfy this conjecture. Adding to fullerene graphs, triangular and quadrangular faces we conceive fuleroid-(3, 4, 5, 6) graphs. We studied the bipartite edge frustration and the maximum independent set problems on the fuleroid-(3, 4, 5, 6) graphs, obtaining tight limits for both problems.
Keywords: Engenharia de Sistemas e Computação
Grafos
Frustração de arestas
Subject CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Program: Programa de Pós-Graduação em Engenharia de Sistemas e Computação
Department : Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Publisher: Universidade Federal do Rio de Janeiro
Issue Date: Apr-2017
Publisher country: Brasil
Language: por
Right access: Acesso Aberto
Appears in Collections:Engenharia de Sistemas e Computação

Files in This Item:
File Description SizeFormat 
878092.pdf7,56 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.