Gráfico transitivo de vértice

En teoría de grafos, un grafo transitivo de vértice es un grafo G tal que para cualesquiera dos vértices v 1 y v 2 del grafo G existe un automorfismo

tal que

En otras palabras, un gráfico es de vértice transitivo si su grupo de automorfismos actúa de forma transitiva con respecto a los vértices [1] . Un grafo es transitivo de vértice si y solo si los resultados de los automorfismos de su complemento son idénticos.

Cualquier gráfico simétrico sin vértices aislados es transitivo de vértice, y cualquier gráfico transitivo de vértice es regular . Sin embargo, no todos los gráficos transitivos de vértice son simétricos (por ejemplo, los bordes de un tetraedro truncado ), y no todos los gráficos regulares son transitivos de vértice (por ejemplo, el gráfico de Frucht y el gráfico de Tietze ).

Ejemplos de grafos finitos

El conjunto de gráficos transitivos de vértice finitos incluye gráficos simétricos (como el gráfico de Petersen , el gráfico de Heawood y los vértices y aristas de poliedros regulares ). Los gráficos de Cayley finitos (como los ciclos al cubo ) son transitivos en los vértices, al igual que los vértices y las aristas de un sólido de Arquímedes (aunque solo 2 de ellos son simétricos). Potočnik, Spiga y Verret crearon un censo de todos los gráficos transitivos de vértice cúbicos conectados (es decir, con vértices de grado 3) con un número de vértices que no superaba los 1280 [2] .

Propiedades

La conectividad de borde de un gráfico transitivo de vértice es igual al grado d , mientras que la conectividad de vértice será al menos 2( d +1)/3 [3] . Si el grado es 4 o menos, o el gráfico también es de borde transitivo , o el gráfico es un gráfico de Cayley mínimo , entonces la conectividad de vértice será d [4] .

Ejemplos de grafos infinitos

Los gráficos transitivos de vértice infinito incluyen:

Dos gráficos transitivos de vértice contables se denominan cuasi-isométricos si la relación de sus funciones de distancia está limitada por abajo y por arriba. Una conjetura bien conocida establece que cualquier gráfico transitivo de vértice infinito es casi isomorfo al gráfico de Cayley . Reinhard Diestel e Imre Leader presentaron un contraejemplo en 2001 [5] . En 2005, Eskin, Fisher y Whyte confirmaron la corrección del contraejemplo [6] .

Véase también

Notas

  1. ↑ Chris Godsil, Gordon Royle. Teoría algebraica de grafos. - Nueva York: Springer-Verlag, 2001. - T. 207 .
  2. ↑ Potočnik P., Spiga P. y Verret G. (2012), Cubic vertex-transitive graphs on up to 1280 vertices , Journal of Symbolic Computation 
  3. ↑ Godsil, C. y Royle, G. Teoría de grafos algebraicos. — Springer Verlag, 2001.
  4. ↑ Babai, L. Informe técnico TR-94-10. - Universidad de Chicago, 1996 . Consultado el 29 de agosto de 2010. Archivado desde el original el 11 de junio de 2010.
  5. ↑ Reinhard Diestel, Líder Imre. Una conjetura sobre un límite de gráficos que no son de Cayley // Journal of Algebraic Combinatorics. - 2001. - T. 14 , núm. 1 . — P. 17–25 . -doi : 10.1023/A : 1011257718029 .
  6. ↑ Alex Eskin, David Fisher, Kevin Whyte. Cuasi-isometrías y rigidez de grupos solubles. — 2005.

Enlaces