Grafo simétrico

En el campo matemático de la teoría de grafos, un grafo G es simétrico si, dado cualquier par de pares de vértices adyacentes u1—v1 y u2—v2 de G, existe un automorfismof: V(G) → V(G)tal quef(u1) = u2 and f(v1) = v2.En otras palabras, un grafo es simétrico si su grupo automórfico actúa transitivamente sobre pares ordenados de vértices adyacentes (es decir, sobre los bordes considerados como teniendo una dirección). Este grafo se denomina a veces también 1-arco-transitivo.Por definición (ignorando u1 y u2), un grafo simétrico sin vértices aislados también debe ser vértice transitivo. Ya que la definición anterior mapea un borde al otro, una grafo simétrico también debe ser arista transitivo. Sin embargo, un grafo arista transitivo no es necesariamente simétrico, ya que a—b puede mapear a c—d, pero no a d—c. Los grafos semi-simétricos, por ejemplo, son arista transitivos y regulares, pero no vértice transitivos.Cada grafo simétrico conectado debe por lo tanto ser a la vez vértice transitivo y arista transitivo, y lo contrario es cierto para los grafos de grado impar. Sin embargo, para los grafos de grado par, existen grafos conectados que son vértice transitivos y arista transitivos, pero no simétricos. Tales grafos son llamados semi-transitivos. el grafo semi-transitivo conectado más pequeño es el grafo de Holt, de grado 4 y con 27 vértices. Confusamente, algunos autores usan el término ""grafo simétrico"" hablando de grafos que son vértice transitivos y arista transitivos, pero no son arco transitivos. Una definición así incluiría los grafos semi-transitivos, que están excluidos en virtud de la definición anterior.Un grafo distancia-transitivo es aquél donde en lugar de considerar pares de vértices adyacentes (es decir, los vértices separados por una arista), la definición comprende dos pares de vértices, cada uno a la misma distancia. Tales grafos son automáticamente simétricos, por definición.Un t-arco es definido como una secuencia de t+1 vértices, tal que dos vértices consecutivos cualesquiera en la secuencia son adyacentes, y cualquier vértice repetido está separado por lo menos 2 pasos. Un grafo t-transitivo es un grafo tal que el grupo automórfico actúa transitivamente sobre t-arcos, pero no sobre (t+1)-arcos. Ya que 1-arcos son simplemente aristas, cada grafo simétrico de grado 3 o mayor debe ser t-transitivo para alguna t, y el valor de t puede ser usado para clasificar los grafos simétricos. Por ejemplo, el cubo es 2-transitivo.