Gráfico de Desargues

En el campo matemático de la teoría de grafos , el grafo de Desargues es un grafo cúbico transitivo de distancia con 20 vértices y 30 aristas. ^[1] Lleva el nombre de Girard Desargues , surge de varias construcciones combinatorias diferentes, tiene un alto nivel de simetría, es el único cubo parcial cúbico no plano conocido y se ha aplicado en bases de datos químicas.

El nombre "gráfico de Desargues" también se ha utilizado para referirse a un gráfico de diez vértices, el complemento del gráfico de Petersen , que también puede formarse como la mitad bipartita del gráfico de Desargues de 20 vértices. ^[2]

Construcciones

Hay varias formas diferentes de construir el gráfico de Desargues:

Se trata del grafo de Petersen generalizado $G (10,3)$ . Para formar el grafo de Desargues de esta manera, se conectan diez de los vértices en un decágono regular y se conectan los otros diez vértices en una estrella de diez puntas que conecta pares de vértices a distancia tres en un segundo decágono. El grafo de Desargues consta de las 20 aristas de estos dos polígonos junto con 10 aristas adicionales que conectan los puntos de un decágono con los puntos correspondientes del otro.
Se trata del grafo de Levi de la configuración de Desargues . Esta configuración consta de diez puntos y diez líneas que describen dos triángulos en perspectiva , su centro de perspectividad y su eje de perspectividad. El grafo de Desargues tiene un vértice para cada punto, un vértice para cada línea y una arista para cada par punto-línea incidente. El teorema de Desargues , llamado así por el matemático francés del siglo XVII Gérard Desargues , describe un conjunto de puntos y líneas que forman esta configuración, y la configuración y el grafo toman su nombre de él.
Es la doble cubierta bipartita del grafo de Petersen , formada al reemplazar cada vértice del grafo de Petersen por un par de vértices y cada arista del grafo de Petersen por un par de aristas cruzadas.
Es el grafo bipartito de Kneser $H 5,2$ . Sus vértices pueden etiquetarse mediante los diez subconjuntos de dos elementos y los diez subconjuntos de tres elementos de un conjunto de cinco elementos, con una arista que conecta dos vértices cuando uno de los conjuntos correspondientes es un subconjunto del otro. De manera equivalente, el grafo de Desargues es el subgrafo inducido del hipercubo de cinco dimensiones determinado por los vértices de peso 2 y peso 3.
El grafo de Desargues es hamiltoniano y se puede construir a partir de la notación MCF : $[5,-5,9,-9] 5$ . Como Erdős conjeturó que para $k > 0$ , el subgrafo del hipercubo $(2 k + 1)$ -dimensional inducido por los vértices de peso $k$ y $k + 1$ es hamiltoniano, la hamiltonicidad del grafo de Desargues no es ninguna sorpresa. (También se deduce de la conjetura más fuerte de Lovász que, a excepción de unos pocos contraejemplos conocidos, todos los grafos transitivos de vértices tienen ciclos hamiltonianos).

Propiedades algebraicas

El grafo de Desargues es un grafo simétrico : tiene simetrías que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Su grupo de simetría tiene orden 240 y es isomorfo al producto de un grupo simétrico en 5 puntos con un grupo de orden 2.

Se puede interpretar esta representación del producto del grupo de simetría en términos de las construcciones del grafo de Desargues: el grupo simétrico en cinco puntos es el grupo de simetría de la configuración de Desargues, y el subgrupo de orden 2 intercambia los roles de los vértices que representan puntos de la configuración de Desargues y los vértices que representan líneas. Alternativamente, en términos del grafo bipartito de Kneser , el grupo simétrico en cinco puntos actúa por separado en los subconjuntos de dos y tres elementos de los cinco puntos, y la complementación de subconjuntos forma un grupo de orden dos que transforma un tipo de subconjunto en el otro. El grupo simétrico en cinco puntos es también el grupo de simetría del grafo de Petersen , y el subgrupo de orden 2 intercambia los vértices dentro de cada par de vértices formados en la construcción de doble cobertura.

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 2 \equiv \pm1 (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)$ . ^[3] Por lo tanto, el grafo de Desargues es uno de los siete únicos grafos de Petersen generalizados simétricos. Entre estos siete grafos se encuentran el grafo cúbico $G$ $(4, 1)$ , el grafo de Petersen $G$ $(5, 2)$ , el grafo de Möbius-Kantor $G$ $(8, 3)$ , el grafo dodecaédrico $G$ $(10, 2)$ y el grafo de Nauru $G$ $(12, 5)$ .

El polinomio característico del gráfico de Desargues es

(x-3)(x-2)^{4}(x-1)^{5}(x+1)^{5}(x+2)^{4}(x+3).\,

Por lo tanto, el gráfico de Desargues es un gráfico integral : su espectro está formado enteramente por números enteros.

Aplicaciones

En química , el gráfico de Desargues se conoce como gráfico de Desargues-Levi ; se utiliza para organizar sistemas de estereoisómeros de compuestos de 5 ligandos . En esta aplicación, los treinta bordes del gráfico corresponden a pseudorrotaciones de los ligandos. ^[4]^[5]

Otras propiedades

El grafo de Desargues tiene un número de cruce rectilíneo 6 y es el grafo cúbico más pequeño con ese número de cruce (secuencia A110507 en la OEIS ). Es el único cubo parcial cúbico no planar conocido . ^[6]

El grafo de Desargues tiene número cromático 2, índice cromático 3, radio 5, diámetro 5 y circunferencia 6. También es un grafo hamiltoniano conexo por 3 vértices y conexo por 3 aristas . Tiene un grosor de libro de 3 y un número de cola de 2. ^[7]

Se conocen todos los gráficos cúbicos de distancia regular . ^[8] El gráfico de Desargues es uno de los 13 gráficos de este tipo.

El gráfico de Desargues se puede incorporar como un mapa regular dual auto-Petrie en la variedad no orientable de género 6, con caras decagonales. ^[9]

Erv Wilson utilizó este diagrama para mostrar los conjuntos de productos de combinación (CPS) del conjunto 3 de 6. Llamó a esta estructura Eikosany.https://www.anaphoria.com/eikosanystructures.pdf

Galería

Gráfico de Desargues coloreado para resaltar varios ciclos.
El índice cromático del gráfico de Desargues es 3.
El número cromático del gráfico de Desargues es 2.

Referencias

^ Weisstein, Eric W. , "Desargues Graph", MathWorld
^ Kagno, IN (1947), "Gráficos de Desargues y Pappus y sus grupos", American Journal of Mathematics , 69 (4), The Johns Hopkins University Press: 859–863, doi :10.2307/2371806, JSTOR 2371806.
^ 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.
^ Balaban, AT; Fǎrcaşiu, D.; Bǎnicǎ, R. (1966), "Gráficos de múltiples desplazamientos 1, 2 en iones de carbonio y sistemas relacionados", Rev. Roum. Chim. , 11 : 1205
^ Mislow, Kurt (1970), "El papel de la pseudorrotación en la estereoquímica de las reacciones de desplazamiento nucleofílico", Acc. Chem. Res. , 3 (10): 321–331, doi :10.1021/ar50034a001
^ Klavžar, Sandi; Lipovec, Alenka (2003), "Cubos parciales como gráficos de subdivisión y como gráficos de Petersen generalizados", Discrete Mathematics , 263 (1–3): 157–165, doi : 10.1016/S0012-365X(02)00575-7
^ Wolz, Jessica, Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
^ Brouwer, AE ; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
^ McMullen, Peter (1992), "Los poliedros regulares de tipo ${$ $p$ $,3}$ con $2$ $p$ vértices", Geometricae Dedicata , 43 (3), doi :10.1007/BF00151518, ISSN 0046-5755