En el campo matemático de la teoría de grafos , un gráfico transitivo por vértices es un gráfico G en el que, dados dos vértices cualesquiera v 1 y v 2 de G , hay cierto automorfismo.
tal que
En otras palabras, un gráfico es transitivo por vértices si su grupo de automorfismo actúa transitivamente sobre sus vértices. [1] Un gráfico es transitivo por vértice si y solo si su complemento del gráfico lo es, ya que las acciones del grupo son idénticas.
Todo gráfico simétrico sin vértices aislados es transitivo por vértices y todo gráfico transitivo por vértices es regular . Sin embargo, no todos los gráficos transitivos por vértices son simétricos (por ejemplo, las aristas del tetraedro truncado ), y no todos los gráficos regulares son transitivos por vértices (por ejemplo, el gráfico de Frucht y el gráfico de Tietze ).
Los gráficos transitivos de vértices finitos incluyen los gráficos simétricos (como el gráfico de Petersen , el gráfico de Heawood y los vértices y aristas de los sólidos platónicos ). Los gráficos finitos de Cayley (como los ciclos de cubos conectados ) también son transitivos por vértices, al igual que los vértices y las aristas de los sólidos de Arquímedes (aunque sólo dos de ellos son simétricos). Potočnik, Spiga y Verret han construido un censo de todos los gráficos transitivos de vértices cúbicos conectados en un máximo de 1280 vértices. [2]
Aunque cada gráfico de Cayley es transitivo por vértices, existen otros gráficos transitivos por vértices que no son gráficos de Cayley. El ejemplo más famoso es el gráfico de Petersen, pero se pueden construir otros, incluidos los gráficos lineales de gráficos no bipartitos transitivos de aristas con grados de vértice impares . [3]
La conectividad de bordes de un gráfico transitivo de vértice conectado es igual al grado d , mientras que la conectividad de vértice será al menos 2 ( d + 1)/3. [1] Si el grado es 4 o menos, o el gráfico también es transitivo de borde , o el gráfico es un gráfico de Cayley mínimo , entonces la conectividad de vértices también será igual a d . [4]
Los gráficos transitivos de vértices infinitos incluyen:
Dos gráficos transitivos de vértices contables se denominan cuasi-isométricos si la relación de sus funciones de distancia está acotada desde abajo y desde arriba. Una conjetura bien conocida afirmaba que todo gráfico transitivo de vértices infinito es cuasi isométrico con respecto a un gráfico de Cayley . Diestel y Leader propusieron un contraejemplo en 2001. [5] En 2005, Eskin, Fisher y Whyte confirmaron el contraejemplo. [6]
