Grafo cúbico

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
El Grafo de Petersen es un grafo cúbico.

En teoría de grafos, un grafo cúbico o grafo trivalente es un grafo cuyos vértices son todos incidentes a exactamente tres aristas. En otras palabras, un grafo cúbico es un grafo 3-regular.

Un grafo bicúbico es un grafo bipartito cúbico.

Historia[editar]

  • 1934: Ronald M. Foster comienza a coleccionar ejemplos de grafos simétricos cúbicos, con lo que se daría inicio al Censo de Foster.[1]
  • 1971: William Tutte conjetura que todos los grafos bicúbicos son ciclos hamiltonianos. Sin embargo, Horton halla un contra-ejemplo de 96-vértices.
  • 2003: Petr Hliněný demuestra que el problema de encontrar el número de cruzamiento (el mínimo número de aristas que se cruzan en un grafo dado) de un grafo cúbico es NP-hard, a pesar de que tienen un grado pequeño. Existen, no obstante, algoritmos de aproximación prácticos para encontrar el número de cruzamiento de grafos cúbicos.

Véase también[editar]

Referencias[editar]

Notas[editar]