Gráfico simétrico
En el campo matemático de la teoría de grafos , un gráfico G es simétrico (o transitivo al arco ) si, dados dos pares de vértices adyacentes u 1 - v 1 y u 2 - v 2 de G , hay un automorfismo
tal que
En otras palabras, un gráfico es simétrico si su grupo de automorfismo actúa transitivamente sobre pares ordenados de vértices adyacentes (es decir, sobre bordes que se consideran que tienen una dirección). [2] Este gráfico a veces también se denomina transitivo de 1 arco [2] o transitivo de bandera . [3]
Por definición (ignorando u 1 y u 2 ), una gráfica simétrica sin vértices aislados también debe ser transitiva por vértice . [1] Dado que la definición anterior asigna una arista a otra, un gráfico simétrico también debe ser transitivo por aristas . Sin embargo, un gráfico de borde transitivo no necesita ser simétrico, ya que a - b podría mapearse a c - d , pero no a d - c . Los gráficos en estrella son un ejemplo simple de ser transitivo por aristas sin ser transitivo a vértice o simétrico. Como ejemplo adicional, gráficos semi-simétricosson transitivos de borde y regulares , pero no transitivos de vértice.
Por tanto, todo gráfico simétrico conectado debe ser tanto transitivo por vértice como por borde transitivo, y lo contrario es cierto para los gráficos de grado impar . [3] Sin embargo, para grados pares , existen grafos conectados que son transitivos de vértice y transitivos de borde, pero no simétricos. [4] Estos gráficos se denominan semitransitivos . [5] El gráfico semitransitivo conectado más pequeño es el gráfico de Holt , con vértices de grado 4 y 27. [1] [6]De manera confusa, algunos autores usan el término "gráfico simétrico" para referirse a un gráfico que es transitivo por vértices y transitivo por bordes, en lugar de un gráfico transitivo por arco. Tal definición incluiría gráficos semitransitivos, que están excluidos de la definición anterior.
Un gráfico transitivo de distancia es aquel en el que en lugar de considerar pares de vértices adyacentes (es decir, vértices separados por una distancia de 1), la definición cubre dos pares de vértices, cada uno con la misma distancia entre sí. Estos gráficos son automáticamente simétricos, por definición. [1]
Un t -arc se define como una secuencia de t + 1 vértices, de manera que dos vértices consecutivos cualesquiera de la secuencia sean adyacentes y los vértices repetidos estén separados por más de 2 pasos. Un gráfico t -transitivo es un gráfico tal que el grupo de automorfismo actúa transitivamente en t -arcs, pero no en ( t + 1) -arcs. Dado que los 1-arcos son simplemente aristas, toda gráfica simétrica de grado 3 o más debe ser t -transitiva para alguna t , y el valor de t puede usarse para clasificar más gráficas simétricas. El cubo es 2-transitivo, por ejemplo. [1]
Ejemplos de
La combinación de la condición de simetría con la restricción de que los gráficos sean cúbicos (es decir, todos los vértices tienen grado 3) produce una condición bastante fuerte, y tales gráficos son lo suficientemente raros como para ser listados. El censo de Foster y sus extensiones proporcionan dichas listas. [7] El censo de Foster fue iniciado en la década de 1930 por Ronald M. Foster mientras trabajaba en Bell Labs , [8] y en 1988 (cuando Foster tenía 92 años [1] ) el censo de Foster actual (enumerando todos los gráficos simétricos cúbicos hasta 512 vértices) se publicó en forma de libro. [9] Los primeros trece elementos de la lista son gráficos simétricos cúbicos con hasta 30 vértices [10] [11](diez de estos también son transitivos a distancia ; las excepciones son las indicadas):
| Vértices | Diámetro | Circunferencia | Grafico | Notas |
|---|---|---|---|---|
| 4 | 1 | 3 | El gráfico completo K 4 | transitiva a distancia, transitiva a 2 arcos |
| 6 | 2 | 4 | El gráfico bipartito completo K 3,3 | transitiva de distancia, transitiva de 3 arcos |
| 8 | 3 | 4 | Los vértices y aristas del cubo | transitiva a distancia, transitiva a 2 arcos |
| 10 | 2 | 5 | El gráfico de Petersen | transitiva de distancia, transitiva de 3 arcos |
| 14 | 3 | 6 | El gráfico de Heawood | transitiva a distancia, transitiva a 4 arcos |
| dieciséis | 4 | 6 | El gráfico de Möbius-Kantor | Transitivo de 2 arcos |
| 18 | 4 | 6 | El gráfico de Pappus | transitiva de distancia, transitiva de 3 arcos |
| 20 | 5 | 5 | Los vértices y aristas del dodecaedro | transitiva a distancia, transitiva a 2 arcos |
| 20 | 5 | 6 | El gráfico de Desargues | transitiva de distancia, transitiva de 3 arcos |
| 24 | 4 | 6 | El gráfico de Nauru (el gráfico de Petersen generalizado G (12,5)) | Transitivo de 2 arcos |
| 26 | 5 | 6 | El gráfico F26A [11] | 1-arco-transitivo |
| 28 | 4 | 7 | El gráfico de Coxeter | transitiva de distancia, transitiva de 3 arcos |
| 30 | 4 | 8 | El gráfico de Tutte-Coxeter | transitiva a distancia, transitiva a 5 arcos |
Otras gráficas cúbicas simétricas bien conocidas son la gráfica de Dyck , la gráfica de Foster y la gráfica de Biggs-Smith . Las diez gráficas de distancia transitiva enumeradas anteriormente, junto con la gráfica de Foster y la gráfica de Biggs-Smith , son las únicas gráficas cúbicas de distancia transitiva.
Los gráficos simétricos no cúbicos incluyen gráficos cíclicos (de grado 2), gráficos completos (de grado 4 o más cuando hay 5 o más vértices), gráficos de hipercubo (de grado 4 o más cuando hay 16 o más vértices) y el Gráficos formados por los vértices y aristas del octaedro , icosaedro , cuboctaedro e icosidodecaedro . El gráfico de Rado forma un ejemplo de un gráfico simétrico con infinitos vértices y grados infinitos.
Propiedades
La conectividad de vértice de un gráfico simétrico es siempre igual al grado d . [3] Por el contrario, para los gráficos transitivos de vértice en general, la conectividad de vértice está delimitada por debajo por 2 ( d + 1) / 3. [2]
Una gráfica t- transitiva de grado 3 o más tiene una circunferencia de al menos 2 ( t - 1). Sin embargo, no hay gráficos t -transitivos finitos de grado 3 o más para t ≥ 8. En el caso de que el grado sea exactamente 3 (gráficos cúbicos simétricos), no hay ninguno para t ≥ 6.
Ver también
- Teoría de grafos algebraicos
- Galería de gráficos con nombre
- Mapa regular
Referencias
- ↑ a b c d e f Biggs, Norman (1993). Teoría de grafos algebraicos (2ª ed.). Cambridge: Cambridge University Press. págs. 118–140. ISBN 0-521-45897-8.
- ^ a b c Godsil, Chris ; Royle, Gordon (2001). Teoría de grafos algebraicos . Nueva York: Springer. pag. 59 . ISBN 0-387-95220-9.
- ↑ a b c Babai, L (1996). "Grupos de automorfismo, isomorfismo, reconstrucción" . En Graham, R; Grötschel, M ; Lovász, L (eds.). Manual de combinatoria . Elsevier.
- ^ Bouwer, Z. (1970). "Gráficos transitivos de vértice y borde, pero no 1-transitivos" . Canad. Matemáticas. Toro. 13 : 231-237. doi : 10.4153 / CMB-1970-047-8 .
- ^ Gross, JL y Yellen, J. (2004). Manual de teoría de grafos . Prensa CRC. pag. 491. ISBN 1-58488-090-2.
- ^ Holt, Derek F. (1981). "Un gráfico que es transitivo de borde pero no transitivo de arco". Revista de teoría de grafos . 5 (2): 201–204. doi : 10.1002 / jgt.3190050210 ..
- ^ Marston Conder , Gráficos simétricos trivalentes en hasta 768 vértices , J. Combin. Matemáticas. Combin. Computación, vol. 20, págs. 41–63
- ^ Foster, RM "Circuitos geométricos de redes eléctricas". Transacciones del Instituto Americano de Ingenieros Eléctricos 51 , 309–317, 1932.
- ^ "El censo de Foster: Censo de RM Foster de gráficos trivalentes simétricos conectados", por Ronald M. Foster, IZ Bouwer, WW Chernoff, B. Monson y Z. Star (1988) ISBN 0-919611-19-2
- ^ Biggs, pág. 148
- ^ a b Weisstein, Eric W., " Gráfico simétrico cúbico ", de Wolfram MathWorld.
enlaces externos
- Gráficos simétricos cúbicos (The Foster Census) . Archivos de datos para todos los gráficos cúbicos simétricos hasta 768 vértices y algunos gráficos cúbicos con hasta 1000 vértices. Gordon Royle, actualizado en febrero de 2001, consultado el 18 de abril de 2009.
- Gráficos simétricos trivalentes (cúbicos) de hasta 10000 vértices . Marston Conder , 2011.
- Teoría de grafos algebraicos
- Familias de gráficos
- Gráficos regulares
