Grafo poliédrico

El diagrama de Schlegel de un poliedro convexo representa sus vértices y aristas como puntos y segmentos de línea recta en un espacio bidimensional, 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 cada grafo poliédrico también es un grafo plano. Además, por el teorema de Balinski, es un grafo 3-vértices-conectado.

De acuerdo con teorema de Steinitz, estas dos propiedades teóricas de grafos son suficientes para caracterizar completamente los grafos poliédricos: son exactamente los grafos planos conectados en 3 vértices. Es decir, siempre que un grafo sea tanto plano como conectado por 3 vértices, existe un poliedro cuyos vértices y aristas forman un grafo isomórfico.[1][2] Dado tal grafo, 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 usando el embebido de Tutte.[3]

Según la conjetura de Tait, todo grafo poliédrico cúbico (es decir, un grafo poliédrico en el que cada vértice incide exactamente en tres aristas) posee un camino hamiltoniano, pero esta conjetura fue refutada por un contraejemplo descubierto por W. T. Tutte, el poliédrico pero no hamiltoniano grafo de Tutte. Si se relaja el requisito de que el grafo sea cúbico, hay grafos poliédricos no hamiltonianos mucho más pequeños. El grafo con la menor cantidad de vértices y aristas es el grafo de Herschel,[4] de 11 vértices y 18 aristas 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]

De forma más exigente, existe una constante α < 1 (exponente de brevedad) y una familia infinita de grafos poliédricos tal que la longitud del camino simple más largo de un grafo de n vértices en la familia es O(n^α).[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

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, ... (sucesión A002840 en OEIS).

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

1, 2, 7, 34, 257, 2606, 32300, 440564, 6384634, 96262938, 1496225352, ... (sucesión A000944 en OEIS).

Un grafo poliédrico es el grafo de un poliedro simple si es cúbico (es decir, en todo vértice confluyen tres aristas), y es el grafo de un poliedro simplicial si es un grafo plano. Los grafos de Halin, grafos formados a partir de un árbol embebido en un plano al agregar un ciclo externo que conecta todas las hojas del árbol, forman otra subclase importante de los grafos poliédricos.

• Weisstein, Eric W. «Polyhedral Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.