(Go: >> BACK << -|- >> HOME <<)

Ir al contenido

Grafo cúbico

De Wikipedia, la enciclopedia libre
La versión para imprimir ya no se admite y puede contener errores de representación. Actualiza los marcadores del navegador y utiliza en su lugar la función de impresión predeterminada del navegador.
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

  • 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 contraejemplo 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

Referencias

Notas

  1. El censo de Foster Archivado el 4 de octubre de 2008 en Wayback Machine.