Conde de Nauru

En teoría de grafos, el gráfico de Nauru  es un gráfico cúbico bipartito simétrico con 24 vértices y 36 aristas. El conde fue nombrado David Epstein por la estrella de doce puntas en la bandera de Nauru . [una]

El número cromático del gráfico es 2, el índice cromático es 3, el diámetro es 4, el radio  es 4 y la circunferencia es 6 [2] . El gráfico es conectado por 3 vértices y conectado por 3 aristas .

Se conocen los gráficos cúbicos más pequeños con cruces 1-8 (secuencia A110507 en OEIS ). El gráfico más pequeño con 8 cruces es el gráfico de Nauru. Hay 5 gráficos cúbicos no isomorfos con 24 vértices y 8 intersecciones [3] . Uno de ellos es Count McGee , también conocido como (3-7) -cell . [cuatro]

Edificio

El gráfico de Nauru es hamiltoniano y puede describirse usando la notación LCF  : [5, −9, 7, −7, 9, −5] 4 . [una]

El gráfico de Nauru también se puede construir como un gráfico de Petersen generalizado G (12, 5) formado por los vértices de un dodecágono , donde los bordes conectan los vértices para formar una estrella de 12 rayos conectando los vértices con un paso de 5.

También es posible una construcción basada en combinatoria . Tomemos tres objetos diferentes y colóquelos en cuatro cajas indistinguibles, no más de un objeto por caja. Hay 24 formas de colocar objetos, lo que corresponde a 24 vértices del gráfico. Si es posible pasar de una ubicación a otra moviendo exactamente un elemento a un cuadro vacío, conectamos dos vértices con un borde. El gráfico de transición de ubicación a ubicación resultante es el gráfico de Nauru.

Propiedades algebraicas

El grupo de automorfismos del grafo de Nauru es un grupo de orden 144. [5] . El grupo es isomorfo al producto directo de los grupos simétricos S 4 y S 3 y actúa transitivamente sobre los vértices, aristas y arcos del gráfico. Por lo tanto, el gráfico de Nauru es simétrico (aunque no transitivo en distancia ). El grafo tiene automorfismos que asignan cualquier vértice a cualquier otro y cualquier borde a cualquier otro. Según la lista de Foster, el gráfico de Nauru es el único gráfico simétrico cúbico con 24 vértices [2] .

Un gráfico de Petersen generalizado G ( n, k ) es transitivo de vértice si y solo si n  = 10 y k  = 2 o si k 2  ≡ ±1 (mod  n ) y es transitivo de borde solo si: ( n, k ) = (4.1), (5.2), (8.3), (10.2), (10.3), (12.5), (24.5) [6] . Por lo tanto, el gráfico de Nauru es uno de los siete gráficos de Petersen generalizados simétricos. Estos siete gráficos incluyen el gráfico cúbico , el gráfico de Petersen , el gráfico de Möbius-Cantor , el gráfico de dodecaedro y el gráfico de Desargues .

El gráfico de Nauru es el gráfico de Cayley del grupo S 4 , un grupo de permutación simétrico de cuatro elementos formado al permutar el primer elemento con otros tres: (1 2), (1 3) y (1 4).

El polinomio característico de la matriz gráfica de Nauru es

de donde se sigue que el gráfico es un número entero , un  gráfico cuyo espectro consta sólo de números enteros.

Propiedades topológicas

El grafo de Nauru tiene dos incrustaciones diferentes a modo de poliedro regular generalizado , en el que las superficies topológicas se dividen en aristas, vértices y caras de tal forma que existe una simetría que toma cualquier bandera (la terna incidente de un vértice, arista, y cara) a cualquier otra bandera [7] .

Una de estas dos incrustaciones forma un toro , por lo que el gráfico de Nauru es un gráfico toroidal :  consta de 12 caras hexagonales junto con 24 vértices y 36 caras de gráficos de Nauru. El gráfico dual de esta incrustación es un gráfico simétrico de 6 regulares con 12 vértices y 36 aristas.

Otra incrustación simétrica del gráfico de Nauru tiene seis caras dodecagonales y forma una superficie de género 4. Su gráfico dual no es un gráfico simple , ya que cada cara comparte tres aristas con otras cuatro caras, sino que es un multigrafo . Este gráfico dual se puede formar a partir del gráfico de un octaedro regular reemplazando cada borde con tres bordes paralelos.

El conjunto de caras de cualquiera de estas dos incrustaciones es el conjunto de polígonos de Petri de la otra incrustación.

Propiedades geométricas

Como todos los gráficos de Petersen generalizados, el gráfico de Nauru se puede representar como puntos en el plano de tal manera que los vértices adyacentes estén a una distancia de uno. Por lo tanto, es un gráfico de unidad de distancia [8] . Este gráfico y el prisma son los únicos gráficos de Petersen generalizados G ( n , p ) que no pueden representarse de tal manera que las simetrías del patrón formen un grupo cíclico de orden n . En cambio, su representación gráfica tiene el grupo diédrico Dih 6 como su grupo de simetría .

Historia

La primera persona en escribir sobre el gráfico de Nauru fue Foster, quien incluyó el gráfico en la lista de todos los gráficos simétricos cúbicos [9] . Una lista completa de gráficos simétricos cúbicos ahora lleva su nombre ( Lista de Foster ) y en esta lista el recuento de Nauru se numera F24A pero no se le da ningún nombre [10] . En 1950 , Coxeter mencionó el gráfico por segunda vez, dando una representación hamiltoniana para ilustrar el artículo y describiendo el gráfico como un gráfico de Levi de la configuración proyectiva descubierta por Zaharias [11] [12] .

En 2003, Ed Pegg Jr. escribió en un artículo en el sitio web de la Asociación Matemática de América que F24A merecía un nombre, pero no lo propuso [13] . Finalmente, en 2007, David Epstein usó el nombre Conde de Nauru porque la bandera de la República de Nauru contiene una estrella de 12 puntas, similar a la que ocurre cuando el gráfico se construye como un gráfico de Petersen generalizado. [una]

Notas

1. ↑ 1 2 3 David Eppstein, Las muchas caras del gráfico de Nauru Archivado desde el original el 21 de julio de 2011. en LiveJournal, 2007.
2. ↑ 1 2 Conder, Dobcsányi, 2002 , p. 40, 41-63.
3. ↑ Pegg, Exoo, 2009 .
4. ↑ Weisstein, Eric W. Graph Crossing Number  en el sitio web de Wolfram MathWorld .
5. ↑ Royle, G. Datos de F024A Archivado el 6 de marzo de 2011 en Wayback Machine .
6. ↑ Frucht, Graver, Watkins, 1971 , pág. 211–218.
7. ↑ McMullen, 1992 , pág. 285–289.
8. ↑ 1 2 Zitnik, Horvat, Pisanski, 2010 .
9. ↑ Foster, 1932 , pág. 309–317.
10. ↑ Bouwer, Chernoff, Monson, Star, 1988 .
11. ↑ Coxeter, 1950 , pág. 413–455.
12. ↑ Zacarías, 1941 , pág. 147–170.
13. ↑ Pegg, 2003 .

Literatura

• M. Conder, P. Dobcsany. Gráficos simétricos trivalentes de hasta 768 vértices. // J. Combina. Matemáticas. Combinar. Computación.. - 2002.
• ET Pegg, G. Exoo. Cruce de gráficas de números // Mathematica Journal. - 2009. - T. 11 .
• R. Frucht, JE Graver, ME Watkins. Los grupos de los gráficos de Petersen generalizados // Actas de la Sociedad Filosófica de Cambridge . - 1971. - T. 70 . -doi : 10.1017/ S0305004100049811 .
• Peter Mc Mullen. Los poliedros regulares de tipo { p , 3} con 2 p vértices // Geometriae Dedicata . - 1992. - T. 43 , núm. 3 . -doi : 10.1007/ BF00151518 .
• Arjana Žitnik, Boris Horvat, Tomaž Pisanski. Todos los gráficos de Petersen generalizados son gráficos de unidad de distancia. - 2010. - T. 1109. - (preprints del IMFM).
• RM Foster. Circuitos geométricos de redes eléctricas // Transacciones del Instituto Americano de Ingenieros Eléctricos . - 1932. - T. 51 . - doi : 10.1109/T-AIEE.1932.5056068 .
• IZ Bouwer, W. W. Chernoff, B. Monson, Z. Star. El censo de crianza. — Centro de Investigación Charles Babbage, 1988.
• HSM Coxeter. Configuraciones autoduales y gráficos regulares // Boletín de la American Mathematical Society. - 1950. - T. 56 . -doi : 10.1090 / S0002-9904-1950-09407-5 .
• M. Zacarías. Untersuchungen über ebene Konfigurationen (124, 163) // Deutsche Mathematik. - 1941. - T. 6 .
• Ed Pegg Jr. Gráficos simétricos cúbicos. — Asociación Matemática de América, 2003.