Conde Goldner - Harari

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de marzo de 2022; la verificación requiere 1 edición .
Conde Goldner - Harari
Lleva el nombre de A. Goldner, F. Harari
picos once
costillas 27
Radio 2
Diámetro 2
Circunferencia 3
automorfismos 12 ( D6 )
Número cromático cuatro
índice cromático ocho
Propiedades

poliedro
plano
cordal
perfecto


ancho de madera = 3
 Archivos multimedia en Wikimedia Commons

En teoría de grafos, el gráfico de Goldner-Harari es un gráfico no dirigido  simple con 11 vértices y 27 aristas. El archivo lleva el nombre de A. Goldner y F. Harari , quienes demostraron en 1975 que es el gráfico plano máximo no hamiltoniano más pequeño [1] [2] [3] . El mismo gráfico ya fue dado como ejemplo de un politopo simplicial no hamiltoniano por Grünbaum en 1967. [4]

Propiedades

El gráfico de Goldner es plano de Harari  : se puede dibujar en un plano sin cruzar los bordes. Cuando se dibuja en el plano, todas las caras del gráfico son triangulares, lo que lo convierte en un gráfico plano máximo . Al igual que cualquier gráfico planar máximo, también está conectado a 3 vértices  : al eliminar dos vértices, el subgrafo queda conectado.

El conde de Goldner es el Harari de los no hamiltonianos . El número más pequeño posible de vértices para gráficos poliédricos no hamiltonianos es 11. Por lo tanto, el gráfico de Goldner-Harari es un ejemplo de un gráfico mínimo 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-Harari proporciona un ejemplo de un gráfico plano con un grosor de libro superior a dos [5] . Con base en la existencia de tales ejemplos, Bernhart y Kainen (Bernhart, Kainen) conjeturaron que el grosor del libro de los gráficos planos puede ser arbitrariamente grande, pero luego se demostró que todos los gráficos planos tienen un grosor del libro que no excede cuatro [6] .

El grosor del libro del gráfico es 3, el número cromático es 4, el índice cromático es 8, la circunferencia es 3, el radio es 2, el diámetro es 2 y el gráfico está conectado por 3 bordes .

El gráfico también es un árbol de 3 , por lo que su ancho de árbol es 3. Como cualquier árbol k , el gráfico es cordal . Como un árbol de 3 planos, el gráfico proporciona un ejemplo de una red de Apolonio .

Geometría

Según el teorema de Steinitz, el gráfico de Goldner-Harari es un gráfico poliédrico  : es plano y conexo en 3, por lo que hay un poliedro convexo que tiene el gráfico de Goldner-Harari como su esqueleto .

Geométricamente, la representación poliédrica del gráfico de Goldner-Harari se puede formar pegando un tetraedro a cada cara de una bipirámide triangular , de la misma manera que se forma un triakistetraedro pegando un tetraedro a cada cara de un octaedro . Es decir, es un poliedro de Klee de una bipirámide triangular [4] [7] . El gráfico dual de Count Goldner-Harari está representado geométricamente por el truncamiento de un prisma triangular .

Propiedades algebraicas

El grupo de automorfismos del gráfico de Goldner-Harari tiene orden 12 y es isomorfo al grupo diédrico D 6 , el grupo de simetría de un hexágono regular que incluye tanto rotaciones como reflexiones.

El polinomio característico del gráfico de Goldner-Harari es .

Notas

  1. ↑ A. Goldner, F.Harary. {{{título}}} // Bol. Matemáticas de Malasia. Soc.. - 1975. - V. 6 , núm. 1 . — Pág. 41–42 . . Véanse también los números 6 (2):33 (1975) y 8 :104-106 (1977). Enlaces de la lista de sitios de las publicaciones de Harari. Archivado el 2 de enero de 2013 en Wayback Machine .
  2. ↑ MB Dillencourt. Poliedros de pequeño orden y sus propiedades hamiltonianas // Revista de Teoría Combinatoria, Serie B. - 1996. - V. 66 . — S. 87–122 . -doi : 10.1006/ jctb.1996.0008 . .
  3. ↑ RC Read, RJ Wilson. Un atlas de gráficos. - Oxford, Inglaterra: Oxford University Press, 1998. - S. 285. .
  4. ↑ 1 2 Branko Grünbaum. Politopos convexos. - Wiley Interscience, 1967. - S. 357. .
  5. ↑ Frank R. Bernhart, Paul C. Kainen. El grosor del libro de un gráfico. - Revista de Teoría Combinatoria, Serie B. - 1979. - V. 27. - S. 320-331. - doi : 10.1016/0095-8956(79)90021-2 . .
  6. ↑ Mihalis Yannakakis. proc. 18 ACM Symp. Teoría de la Computación (STOC). - 1986. - S. 104-108. -doi : 10.1145/ 12130.12141 . .
  7. ↑ Gunther Ewald. Circuitos hamiltonianos en complejos simpliciales // Geometriae Dedicata. - 1973. - Vol. 2 , número. 1 . — S. 115–125 . -doi : 10.1007/ BF00149287 . .

Enlaces