En el campo matemático de la teoría de grafos , el grafo de Goldner-Harary es un grafo simple no dirigido con 11 vértices y 27 aristas. Recibe su nombre en honor a A. Goldner y Frank Harary , quienes demostraron en 1975 que era el grafo plano maximalista no hamiltoniano más pequeño . [1] [2] [3] El mismo grafo ya había sido dado como ejemplo de un poliedro simplicial no hamiltoniano por Branko Grünbaum en 1967. [4]
El grafo de Goldner-Harary es un grafo plano : se puede dibujar en el plano sin que ninguna de sus aristas se cruce. Cuando se dibuja en un plano, todas sus caras son triangulares, lo que lo convierte en un grafo plano maximalista . Como ocurre con todos los grafos planos maximalistas, también es conexo por 3 vértices : la eliminación de dos de sus vértices deja un subgrafo conexo .
El grafo de Goldner-Harary también es no hamiltoniano . El número mínimo posible de vértices para un grafo poliédrico no hamiltoniano es 11. Por lo tanto, el grafo de Goldner-Harary es un ejemplo mínimo de grafos de este tipo. Sin embargo, el grafo de Herschel , otro poliedro no hamiltoniano con 11 vértices, tiene menos aristas.
Como grafo planar maximalista no hamiltoniano, el grafo de Goldner-Harary proporciona un ejemplo de grafo planar con un grosor de libro mayor que dos. [5] Basándose en la existencia de tales ejemplos, Bernhart y Kainen conjeturaron que el grosor de libro de los grafos planares podría hacerse arbitrariamente grande, pero posteriormente se demostró que todos los grafos planares tienen un grosor de libro de cuatro como máximo. [6]
Tiene un grosor de libro de 3, número cromático de 4, índice cromático de 8, circunferencia de 3, radio de 2, diámetro de 2 y es un grafo de 3 aristas conexas .
También es un árbol de 3 elementos y, por lo tanto, tiene un ancho de árbol de 3. Como cualquier árbol k , es un grafo cordal . Como árbol de 3 elementos planar, constituye un ejemplo de red apolínea .
Según el teorema de Steinitz , el grafo de Goldner-Harary es un grafo poliédrico : es plano y 3-conexo, por lo que existe un poliedro convexo que tiene como esqueleto al grafo de Goldner-Harary .
Geométricamente, un poliedro que representa el grafo de Goldner-Harary se puede formar pegando un tetraedro en cada cara de una bipirámide triangular , de manera similar a la forma en que se forma un triakis octaedro pegando un tetraedro en cada cara de un octaedro . Es decir, es el Kleetope de la bipirámide triangular. [4] [7] El grafo dual del grafo de Goldner-Harary se representa geométricamente por el truncamiento del prisma triangular .
El grupo de automorfismos del grafo de Goldner-Harary es de orden 12 y es isomorfo al grupo diedro D 6 , el grupo de simetrías de un hexágono regular , que incluye tanto rotaciones como reflexiones.
El polinomio característico del gráfico de Goldner-Harary es: .
