En la teoría de grafos geométricos , una rama de las matemáticas , un grafo poliédrico es el grafo no dirigido formado a partir de los vértices y las aristas de un poliedro convexo . Alternativamente, en términos puramente de teoría de grafos, los grafos poliédricos son los grafos planos con 3 vértices conectados .
El diagrama de Schlegel de un poliedro convexo representa sus vértices y aristas como puntos y segmentos de línea en el plano euclidiano , formando una subdivisión de un polígono convexo exterior en polígonos convexos más pequeños (un dibujo convexo del grafo del poliedro). No tiene cruces, por lo que todo grafo poliédrico es también un grafo plano . Además, por el teorema de Balinski , es un grafo conexo de 3 vértices .
Según el teorema de Steinitz , estas dos propiedades de la teoría de grafos son suficientes para caracterizar completamente los grafos poliédricos: son exactamente los grafos planares conexos por 3 vértices. Es decir, siempre que un grafo sea tanto planar como conexo por 3 vértices, existe un poliedro cuyos vértices y aristas forman un grafo isomorfo . [1] [2] Dado un grafo de este tipo, se puede encontrar una representación del mismo como una subdivisión de un polígono convexo en polígonos convexos más pequeños utilizando la incrustación de Tutte . [3]
Tait conjeturó que cada grafo poliédrico cúbico (es decir, un grafo poliédrico en el que cada vértice incide exactamente en tres aristas) tiene un ciclo hamiltoniano , pero esta conjetura fue refutada por un contraejemplo de WT Tutte , el grafo de Tutte poliédrico pero no hamiltoniano . Si uno relaja el requisito de que el grafo sea cúbico, hay grafos poliédricos no hamiltonianos mucho más pequeños. El grafo con menos vértices y aristas es el grafo de Herschel de 11 vértices y 18 aristas , [4] y también existe un grafo poliédrico no hamiltoniano de 11 vértices en el que todas las caras son triángulos, el grafo de Goldner-Harary . [5]
Más fuertemente, existe una constante (el exponente de acortamiento ) y una familia infinita de grafos poliédricos tales que la longitud del camino simple más largo de un grafo de -vértice en la familia es . [6] [7]
Duijvestijn proporciona un recuento de los grafos poliédricos con hasta 26 aristas; [8] El número de estos grafos con 6, 7, 8, ... aristas es
También se pueden enumerar los grafos poliédricos por su número de vértices: para grafos con 4, 5, 6, ... vértices, el número de grafos poliédricos es
Los grafos de los sólidos platónicos se han denominado grafos platónicos . Además de tener todas las demás propiedades de los grafos poliédricos, son grafos simétricos y todos ellos tienen ciclos hamiltonianos . [9] Hay cinco de estos grafos:
Un grafo poliédrico es el grafo de un poliedro simple si es cúbico (cada vértice tiene tres aristas), y es el grafo de un poliedro simplicial si es un grafo plano maximalista . Por ejemplo, los grafos tetraédricos, cúbicos y dodecaédricos son simples; los grafos tetraédricos, octaédricos e icosaédricos son simpliciales.
Los grafos de Halin , grafos formados a partir de un árbol plano incrustado añadiendo un ciclo externo que conecta todas las hojas del árbol, forman otra subclase importante de grafos poliédricos.
