Diâmetro de grafos fulerenes e transversalidade de ciclos ímpares de fuleróides-(3, 4, 5, 6)

• Ano de defesa: 2017
• Autor(a) principal: Nicodemos, Diego de Souza
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Brasil; Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia; Programa de Pós-Graduação em Engenharia de Sistemas e Computação; UFRJ
• Palavras-chave em Português: Engenharia de Sistemas e Computação; Grafos; Frustração de arestas; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://hdl.handle.net/11422/10191

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.