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