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. Lleva el nombre de A. Goldner y Frank Harary , quienes demostraron en 1975 que era el gráfico plano máximo no hamiltoniano más pequeño . [1] [2] [3] El mismo gráfico ya se había dado como ejemplo de un poliedro simplicial no hamiltoniano por Branko Grünbaum en 1967. [4]
Gráfico de Goldner-Harary | |
---|---|
Lleva el nombre de | A. Goldner, Frank Harary |
Vértices | 11 |
Bordes | 27 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 3 |
Automorfismos | 12 ( D 6 ) |
Número cromático | 4 |
Índice cromático | 8 |
Propiedades | Poliédrica planar Chordal perfecto Treewidth 3 |
Tabla de gráficos y parámetros |
Propiedades
El gráfico de Goldner-Harary es un gráfico plano : se puede dibujar en el plano sin que ninguno de sus bordes se cruce. Cuando se dibuja en un plano, todas sus caras son triangulares, lo que lo convierte en un gráfico plano máximo . Al igual que con todo gráfico plano máximo, también está conectado por 3 vértices : la eliminación de dos de sus vértices deja un subgráfico conectado .
El gráfico de Goldner-Harary tampoco es hamiltoniano . El menor número posible de vértices para una gráfica poliédrica no hamiltoniana es 11. Por lo tanto, la gráfica de Goldner-Harary es un ejemplo mínimo de gráficas de este tipo. Sin embargo, el gráfico de Herschel , otro poliedro no hamiltoniano con 11 vértices, tiene menos aristas.
Como gráfico plano máximo no hamiltoniano, el gráfico de Goldner-Harary proporciona un ejemplo de un gráfico plano con un grosor de libro superior a dos. [5] Basándose en la existencia de tales ejemplos, Bernhart y Kainen conjeturaron que el grosor del libro de las gráficas planas podría hacerse arbitrariamente grande, pero posteriormente se demostró que todas las gráficas planas tienen un grosor de libro como máximo de cuatro. [6]
Tiene grosor de libro 3, número cromático 4, índice cromático 8, circunferencia 3, radio 2, diámetro 2 y es un gráfico de 3 bordes conectados .
También es un árbol de 3 , y por lo tanto tiene un ancho de árbol de 3. Como cualquier árbol k , es un grafo cordal . Como un árbol de 3 planos, forma un ejemplo de una red apolínea .
Geometría
Según el teorema de Steinitz , el gráfico de Goldner-Harary es un gráfico poliédrico : es plano y está conectado en 3, por lo que existe un poliedro convexo que tiene el gráfico de Goldner-Harary como su esqueleto .
Geométricamente, un poliedro que representa el gráfico de Goldner-Harary puede formarse pegando un tetraedro en cada cara de una bipirámide triangular , de manera similar a como 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 gráfico dual del gráfico de Goldner-Harary está representado geométricamente por el truncamiento del prisma triangular .
Propiedades algebraicas
El grupo de automorfismo del gráfico 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 reflejos.
El polinomio característico del gráfico de Goldner-Harary es:.
Referencias
- ^ Goldner, A .; Harary, F. (1975), "Nota sobre un gráfico planar máximo no hamiltoniano más pequeño", Bull. Matemáticas de Malasia. Soc. , 6 (1): 41–42. Ver también la misma revista 6 (2): 33 (1975) y 8 : 104-106 (1977). Referencia de la lista de publicaciones de Harary .
- ^ Dillencourt, MB (1996), "Poliedros de órdenes pequeños y sus propiedades hamiltonianas", Journal of Combinatorial Theory, Serie B , 66 : 87-122, doi : 10.1006 / jctb.1996.0008.
- ^ Leer, RC; Wilson, RJ (1998), An Atlas of Graphs , Oxford, Inglaterra: Oxford University Press, pág. 285.
- ^ a b Grünbaum, Branko (1967), Convex Polytopes , Wiley Interscience, pág. 357. Misma página, 2a ed., Textos de Posgrado en Matemáticas 221, Springer-Verlag, 2003, ISBN 978-0-387-40409-7 .
- ^ Bernhart, Frank R .; Kainen, Paul C. (1979), "El grosor del libro de un gráfico", Journal of Combinatorial Theory , Serie B, 27 (3): 320–331, doi : 10.1016 / 0095-8956 (79) 90021-2. Ver en particular la Figura 9.
- ^ Yannakakis, Mihalis (1986), "Cuatro páginas son necesarias y suficientes para gráficos planos", Proc. 18 ° ACM Symp. Teoría de la Computación (STOC) , págs. 104–108, doi : 10.1145 / 12130.12141.
- ^ Ewald, Günter (1973), "Circuitos hamiltonianos en complejos simpliciales", Geometriae Dedicata , 2 (1): 115-125, doi : 10.1007 / BF00149287.
enlaces externos
- Weisstein, Eric W. "Gráfico de Goldner-Harary" . MathWorld .