Diâmetro de Grafos Fulerenes e Transversalidade de Ciclos Ímpares de Fuleróides-(3,4,5,6)
Authors:
Autores
| Person role | Person | |
|---|---|---|
|
6426 |
414,413,2913,2914
|
|
|
6425 |
414,413,2913,2914
|
|
|
6424 |
414,413,2913,2914
|
|
|
6427 |
414,413,2913,2914
|
Informations:
Pesc publication
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 [Raiz(5n/3)]-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.
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 [SquareRoot(5n/3)]-11. 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.