En el campo matemático de la teoría de grafos , un grafo simétrico cero es un grafo conectado en el que cada vértice tiene exactamente tres aristas incidentes y, para cada dos vértices, hay una simetría única que lleva de un vértice al otro. Un gráfico de este tipo es un gráfico de vértice transitivo, pero no puede ser un gráfico de borde transitivo : el número de simetrías es igual al número de vértices, demasiado pocos para llevar cada borde a cada otro borde. [1]
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
El nombre de esta clase de gráficos fue acuñado por RM Foster en una carta de 1966 a HSM Coxeter . [2] En el contexto de la teoría de grupos , las gráficas simétricas cero también se denominan representaciones gráficas regulares de sus grupos de simetría. [3]
Ejemplos de
El gráfico simétrico cero más pequeño es un gráfico no plano con 18 vértices. [4] Su notación LCF es [5, −5] 9 .
Entre las gráficas planas , las gráficas cuboctaédrica truncada y icosidodecaédrica truncada también son simétricas cero. [5]
Estos ejemplos son todos gráficos bipartitos . Sin embargo, existen ejemplos más grandes de gráficos simétricos cero que no son bipartitos. [6]
Estos ejemplos también tienen tres clases de simetría (órbitas) diferentes de aristas. Sin embargo, existen gráficos simétricos cero con solo dos órbitas de aristas. El gráfico más pequeño de este tipo tiene 20 vértices, con notación LCF [6,6, -6, -6] 5 . [7]
Propiedades
Cada grafo finito simétrico cero es un grafo Cayley , una propiedad que no siempre es válida para grafos transitivos de vértice cúbicos de manera más general y que ayuda en la solución de tareas de enumeración combinatoria relativas a grafos simétricos cero. Hay 97687 gráficos simétricos cero en hasta 1280 vértices. Estos gráficos forman el 89% de los gráficos de Cayley cúbicos y el 88% de todos los gráficos cúbicos transitivos de vértice conectados en el mismo número de vértices. [8]
¿Cada grafo simétrico cero finito contiene un ciclo hamiltoniano ?
Todos los gráficos simétricos cero conectados finitos conocidos contienen un ciclo hamiltoniano , pero se desconoce si todo gráfico simétrico cero conectado finito es necesariamente hamiltoniano. [9] Este es un caso especial de la conjetura de Lovász de que (con cinco excepciones conocidas, ninguna de las cuales es simétrica cero) cada grafo transitivo de vértice conectado finito y cada grafo de Cayley finito es hamiltoniano.
Ver también
- Gráfico semi-simétrico , gráficos que tienen simetrías entre cada dos aristas pero no entre cada dos vértices (invirtiendo los roles de aristas y vértices en la definición de grafos simétricos cero)
Referencias
- ^ Coxeter, Harold Scott MacDonald ; Frucht, Roberto ; Powers, David L. (1981), gráficos simétricos cero , Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], Nueva York-Londres, ISBN 0-12-194580-4, MR 0658666
- ^ Coxeter, Frucht y Powers (1981) , p. ix.
- ^ Lauri, Josef; Scapellato, Raffaele (2003), Temas de Automorfismos Gráficos y Reconstrucción , Textos de Estudiantes de la Sociedad Matemática de Londres, Cambridge University Press, p. 66, ISBN 9780521529037.
- ^ Coxeter, Frucht y Powers (1981) , Figura 1.1, p. 5.
- ^ Coxeter, Frucht y Powers (1981) , págs. 75 y 80.
- ^ Coxeter, Frucht y Powers (1981) , p. 55.
- ^ Conder, Marston DE ; Pisanski, Tomaž ; Žitnik, Arjana (2017), "Gráficos transitivos de vértice y sus tipos de arco", Ars Mathematica Contemporanea , 12 (2): 383–413, arXiv : 1505.02029 , doi : 10.26493 / 1855-3974.1146.f96 , MR 3646702
- ^ Potočnik, Primož; Spiga, Pablo; Verret, Gabriel (2013), "Gráficos transitivos de vértice cúbico en hasta 1280 vértices", Journal of Symbolic Computation , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016 / j.jsc.2012.09.002 , MR 2996891.
- ^ Coxeter, Frucht y Powers (1981) , p. 10.