Gráfico de Nauru

Gráfico cúbico bipartito simétrico de 24 vértices

En el campo matemático de la teoría de grafos , el grafo de Nauru es un grafo cúbico , bipartito y simétrico con 24 vértices y 36 aristas. David Eppstein le puso ese nombre en honor a la estrella de doce puntas de la bandera de Nauru . ^[1]

Tiene número cromático 2, índice cromático 3, diámetro 4, radio 4 y circunferencia 6. ^[2] También es un grafo con 3 vértices conectados y 3 aristas conectadas . Tiene un grosor de libro de 3 y un número de cola de 2. ^[3]

El grafo de Nauru requiere al menos ocho cruces en cualquier dibujo del mismo en el plano. Es uno de los tres grafos no isomorfos empatados por ser el grafo cúbico más pequeño que requiere ocho cruces. Otro de estos tres grafos es el grafo de McGee , también conocido como la jaula (3-7) . ^{[4] [5]}

Construcción

El gráfico de Nauru es hamiltoniano y se puede describir mediante la notación MCF  : [5, −9, 7, −7, 9, −5] ⁴ . ^[1]

El grafo de Nauru también se puede construir como el grafo de Petersen generalizado G (12, 5) que está formado por los vértices de un dodecágono conectados a los vértices de una estrella de doce puntas en el que cada punta de la estrella está conectada a los puntos a cinco pasos de ella.

También existe una construcción combinatoria del grafo de Nauru. Se toman tres objetos distinguibles y se colocan en cuatro cajas distinguibles, no más de un objeto por caja. Hay 24 maneras de distribuir los objetos de esta manera, correspondientes a los 24 vértices del grafo. Si es posible pasar de un estado a otro moviendo exactamente un objeto desde su ubicación actual a una caja vacía, entonces los vértices correspondientes a los dos estados se unen mediante una arista. El grafo de transición de estado resultante es el grafo de Nauru.

Propiedades algebraicas

El grupo de automorfismos del grafo de Nauru es un grupo de orden 144. ^[6] Es isomorfo al producto directo de los grupos simétricos S ₄ y S ₃ y actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por tanto, el grafo de Nauru es un grafo simétrico (aunque no transitivo en distancia ). Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Según el censo de Foster , el grafo de Nauru es el único grafo cúbico simétrico sobre 24 vértices. ^[2]

El grafo de Petersen generalizado G ( n,k ) es transitivo por vértices si y solo si n  = 10 y k  =2 o si k ²  ≡ ±1 (mod  n ) y es transitivo por aristas solo en los siguientes siete casos: ( n,k ) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). ^[7] Por lo tanto, el grafo de Nauru es uno de los siete grafos de Petersen generalizados simétricos. Entre estos siete grafos se encuentran el grafo cúbico , el grafo de Petersen , el grafo de Möbius-Kantor , el grafo dodecaédrico y el grafo de Desargues . ${\displaystyle G(4,1)}$ ${\displaystyle G(5,2)}$ ${\displaystyle G(8,3)}$ ${\displaystyle G(10,2)}$ ${\displaystyle G(10,3)}$

El grafo de Nauru es un grafo de Cayley de S ₄ , el grupo simétrico de permutaciones de cuatro elementos, generado por las tres formas diferentes de intercambiar el primer elemento con uno de los otros tres: (1 2), (1 3) y (1 4).

El polinomio característico del grafo de Nauru es igual a

${\displaystyle (x-3)(x-2)^{6}(x-1)^{3}x^{4}(x+1)^{3}(x+2)^{6}(x+3),\ }$

convirtiéndolo en un gráfico integral , es decir, un gráfico cuyo espectro consiste enteramente en números enteros.

• 
  Incrustación simétrica en un toro formado al pegar los bordes opuestos de un hexágono regular
• 
  Gráfico de Petersen generalizado , coloreado y etiquetado como un gráfico de Cayley de S ₄
• 
  Matriz de adyacencia . Cada borde está representado por dos entradas ubicadas simétricamente en el mismo color.
• 
  Dibujo uniplanar con 8 cruces
• 
  24 orientaciones de un octaedro rodante sobre una cuadrícula triangular , dibujado sobre un toro hexagonal
• 
  24 configuraciones de un cubo de Rubik 2×2×2 alcanzables mediante medias vueltas de 180°

Propiedades topológicas

Una incrustación simétrica del gráfico de Nauru en una superficie de género 4, con seis caras dodecagonales.

El gráfico de Nauru tiene dos incrustaciones diferentes como poliedro regular generalizado : una superficie topológica dividida en aristas, vértices y caras de tal manera que hay una simetría al tomar cualquier bandera (un triple incidente de un vértice, una arista y una cara) en cualquier otra bandera. ^[8]

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

La otra incrustación simétrica del grafo de Nauru tiene seis caras dodecagonales y forma una superficie de género 4. Su dual no es un grafo simple , ya que cada cara comparte tres aristas con otras cuatro caras, sino un multigrafo . Este dual se puede formar a partir del grafo de un octaedro regular reemplazando cada arista por un haz de tres aristas paralelas.

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

Propiedades geométricas

El gráfico de Nauru como gráfico de distancia unitaria, de Žitnik, Horvat y Pisanski (2010).

Al igual que todos los grafos de Petersen generalizados, el grafo de Nauru puede representarse mediante puntos en el plano de tal manera que los vértices adyacentes estén separados por una distancia unitaria; es decir, es un grafo de distancia unitaria . ^[9] Este y los prismas son los únicos grafos de Petersen generalizados G ( n , p ) que no pueden representarse de tal manera que las simetrías del dibujo formen un grupo cíclico de orden n . En cambio, su representación en grafo de distancia unitaria tiene como grupo de simetría el grupo diedro Dih ₆ .

Historia

La primera persona que escribió sobre el grafo de Nauru fue RM Foster , en un esfuerzo por recopilar todos los grafos cúbicos simétricos. ^[10] La lista completa de grafos cúbicos simétricos ahora lleva su nombre, el Censo Foster , y dentro de esta lista, el grafo de Nauru está numerado como grafo F24A, pero no tiene un nombre específico. ^[11] En 1950, HSM Coxeter citó el grafo una segunda vez, dando la representación hamiltoniana utilizada para ilustrar este artículo y describiéndolo como el grafo de Levi de una configuración proyectiva descubierta por Zacharias. ^{[12] [13]}

En 2003, Ed Pegg escribió en su columna online de la MAA que el F24A merece un nombre, pero no lo propuso. ^[14] Finalmente, en 2007, David Eppstein utilizó el nombre de gráfico de Nauru porque la bandera de la República de Nauru tiene una estrella de 12 puntas similar a la que aparece en la construcción del gráfico como un gráfico de Petersen generalizado. ^[1]

Referencias

1. Eppstein, D. , Las múltiples caras del gráfico de Nauru, 2007.
2. Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes de hasta 768 vértices". J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
3. Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
4. Sloane, N. J. A. (ed.). "Secuencia A110507 (Número de nodos en el grafo cúbico más pequeño con número de cruces n)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS..
5. Pegg, ET ; Exoo, G. (2009), "Gráficos de números cruzados", Mathematica Journal , 11 (2), doi : 10.3888/tmj.11.2-2 , archivado desde el original el 2019-03-06 , consultado el 2010-01-02.
6. Royle, G. Datos de F024A Archivados el 6 de marzo de 2011 en Wayback Machine.
7. Frucht, R. ; Graver, JE; Watkins, ME (1971), "Los grupos de los grafos de Petersen generalizados", Actas de la Sociedad Filosófica de Cambridge , 70 (2): 211–218, Bibcode :1971PCPS...70..211F, doi :10.1017/S0305004100049811, S2CID  122686848.
8. McMullen, Peter (1992), "Los poliedros regulares de tipo { p , 3} con 2 p vértices", Geometriae Dedicata , 43 (3): 285–289, doi :10.1007/BF00151518, S2CID  119591683.
9. Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Todos los gráficos de Petersen generalizados son gráficos de unidades de distancia (PDF) , preimpresiones de IMFM, vol. 1109.
10. Foster, RM (1932), "Circuitos geométricos de redes eléctricas", Transacciones del Instituto Americano de Ingenieros Eléctricos , 51 (2): 309–317, doi :10.1109/T-AIEE.1932.5056068, S2CID  51638449.
11. Bouwer, IZ; Chernoff, WW; Monson, B.; Star, Z (1988), El censo de Foster , Centro de investigación Charles Babbage.
12. Coxeter, HSM (1950), "Configuraciones autoduales y grafos regulares", Boletín de la Sociedad Matemática Americana , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5.
13. Zacharias, M. (1941), "Untersuchungen über ebene Konfigurationen (124, 163)", Deutsche Mathematik , 6 : 147-170.
14. Pegg, Ed (2003), Gráficos cúbicos simétricos, Asociación Matemática de América.