Grafo cúbico

O grafo de Petersen é um grafo cúbico.

O grafo bipartido completo $K_{3,3}$ é um exemplo de grafo bicúbico

O Grafo de Frucht, o menor grafo cúbico assimétrico.

No campo da matemática da teoria dos grafos, um grafo cúbico é um grafo regular no qual todos os vértices tem grau três. Em outras palavras um grafo cúbico é um grafo 3-regular. Grafos cúbicos são também chamados grafos trivalentes.

Um grafo bicúbico é um grafo bipartido cúbico.

Simetria

Em 1932, Ronald M. Foster começou a recolher exemplos de grafos simétricos cúbicos, formando o início do censo de Foster. Muitos grafos individuais conhecidos são cúbicos e simétricos, incluindo o grafo de Petersen, o grafo de Nauru, o grafo de Coxeter, o grafo de Tutte–Coxeter, o grafo de Dyck, o grafo de Foster e o grafo de Biggs-Smith.

W. T. Tutte classificou os grafos simétricos cúbicos pelo menor número inteiro s tal que cada dois caminhos orientados de comprimento s podem ser mapeados entre si por exatamente uma simetria do grafo. Ele mostrou que s é no máximo 5, e deu exemplos de grafos com cada valor possível de s de 1 a 5.

Grafos cúbicos semi-simétricos incluem o grafo de Gray (o menor grafo cúbico semi-simétrico), o grafo de Ljubljana, e o gaiola-12 de Tutte.

O grafo de Frucht é o menor grafo cúbico sem qualquer simetria: possui apenas um único automorfismo de grafos, o automorfismo identidade.

Coloração e conjuntos independentes

De acordo com o teorema de Brooks todo grafo cúbico com exceção do grafo completo K₄ pode ser colorido com no máximo três cores. Portanto, todo grafo cúbico diferente de K ₄ tem um conjunto independente de pelo menos n/3 vértices, onde n é o número de vértices no grafo: por exemplo, a maior classe de cor em uma 3-coloração tem pelo menos estes vértices.

De acordo com o teorema de Vizing todo grafo cúbico necessita três ou quatro cores para uma coloração de arestas. Uma 3-aresta-coloração é conhecida como uma coloração Tait, e forma uma partição das arestas do grafo em três acoplamentos perfeitos. Pelo teorema de coloração de linhas de König todo grafo bicúbico tem uma coloração de Tait.

Os grafos cúbicos sem ponte que não tem uma coloração de Tait são conhecidos como snarks. Eles incluem o grafo de Petersen, grafo de Tietze, os snarks Blanuša, o snark flor, o snark dupla-estrela, o snark Szekeres e o snark Watkins.

Existe um número infinito de snarks distintos.

Hamiltonicidade

Houve muita pesquisa sobre Hamiltonicidade de grafos cúbicos. Em 1880, P.G. Tait conjecturou que todo grafos poliédricos cúbicos tem um circuito Hamiltoniano. William Thomas Tutte forneceu um contra-exemplo para a conjectura de Tait, o grafo de Tutte de 46 vértices, em 1946. Em 1971, Tutte conjecturou que todos os grafos bicúbicos são hamiltonianos. No entanto, José Horton proporcionou um contra-exemplo com 96 vértices, o grafo de Horton. Mais tarde Mark Ellingham, construíu mais dois contra-exemplos: os grafos de Ellingham-Horton. A conjectura de Barnette, uma combinação de conjecturas de Tait e Tutte ainda aberta, afirma que todo grafo bicúbico poliédrico é hamiltoniano. Quando um grafo cúbico é hamiltoniano, a notação LCF permite que ele seja representada de forma concisa.

Se um grafo cúbico é escolhido aleatoriamente entre todos os grafos cúbicos de n-vértices, então é bem provável que seja Hamiltoniano. a proporção de grafos cúbicos de n-vértices que são Hamiltonianos tende a um no limite a medida que n vai para o infinito.

David Eppstein conjecturou que todo grafo cúbico de n-vértices tem no máximo 2^n/3 (aproximadamente 1260ⁿ) ciclos hamiltonianos distintos, e exemplificou com grafos cúbicos com esta quantidade de ciclos. O melhor limite superior que foi até agora comprovado no número de ciclos hamiltonianos distintos é 1,276ⁿ.

Outras propriedades

O comprimento do caminho de quaisquer grafo cúbico de n-vértices é no máximo n/6. No entanto, o limite inferior melhor conhecido no comprimento do caminho de grafos cúbicos é menor, 0.082n.

É consequência do lema do aperto de mãos, provado por Leonhard Euler em 1736 como parte do primeiro trabalho sobre teoria dos grafos, que todo grafo cúbico tem um número par de vértices.

Algoritmos e complexidade

Vários pesquisadores têm estudado a complexidade de tempo exponencial de algoritmos restritos a grafos cúbicos. Por exemplo, através da aplicação de programação dinâmica para a decomposição do caminho do grafo, Fomin e Høie mostraram como encontrar os seus conjuntos independentes máximos em tempo O(n^n/6 + o(n)).

História

• 1880: Peter Guthrie Tait conjeturou que cada grafo sem pontes cúbico planar tem um circuito hamiltoniano. William Thomas Tutte encontrou um contra-exemplo: un grafo de 46 vértices (agora com o seu nome) em 1946.

• 1934: Ronald M. Foster começou a colecionar exemplos de grafos simétricos cúbicos, com o que iria iniciar o Censo de Foster.

• 1971: William Tutte conjetura que todos os grafos bicúbicos são ciclos hamiltonianos. Entretanto, Horton proporciona un grafo de contra-exemplo, com 96-vértices.

• 2003: Petr Hliněný mostra que o problema de encontrar o número de cruzamento (o número mínimo de arestas que cruzam um dado grafo) de um grafo cúbico é NP-hard, apesar de terem um grau pequeno. Existem, não obstante, algoritmos de aproximacão práticos para encontrar o número de cruzamento de grafos cúbicos.