Transitividade de vértice e a propriedade de troca de arestas

Question

Um grafo simples e não direcionado$G=(V,E)$é dito ser transitivo de vértice se para qualquer$a,b\in V$existe um isomorfismo grafo$\varphi:V\to V$de tal modo que$\varphi(a) = b$.

Dizemos que um gráfico$G=(V,E)$tem a propriedade de troca de arestas se para qualquer aresta$e = \{x,y\} \in E$existe um isomorfismo grafo$\varphi:V\to V$de tal modo que$\varphi(x) = y$e$\varphi(y) = x$.

Alguma dessas propriedades implica a outra para grafos conectados?

Answer 1

Como Ekin diz nos comentários, para grafos conectados, a propriedade de troca de arestas implica transitividade de vértice por meio da composição das trocas de arestas ao longo de um caminho.

A outra implicação não é verdadeira. Um grafo é simétrico se para qualquer par de vértices adjacentes$(u_1,v_1)$e$(u_2,v_2)$há um automorfismo enviando$u_1$para$u_2$e$v_1$para$v_2$. Observe que isso é mais forte que a transitividade de aresta, porque podemos especificar a maneira como as extremidades da aresta são mapeadas para as extremidades da outra aresta (portanto, esse grafo também é chamado de arco transitivo ).

Agora, a Wikipedia afirma que existem grafos que são transitivos de vértice e transitivos de aresta, mas não simétricos. Tal grafo não pode ter a propriedade de troca de arestas, caso contrário, poderíamos enviar qualquer par de vértices adjacentes para outro par de vértices adjacentes usando transitividade de arestas e então trocando as arestas, se necessário.

Com relação à conexão entre transitividade de vértice, transitividade de aresta e propriedade de troca de aresta: o grafo de prisma triangular tem a propriedade de troca de aresta e, portanto, é transitivo de vértice, mas não é transitivo de aresta. Não consigo pensar em um gráfico que seja transitivo por vértice, mas não transitivo por arestas, nem tenha a propriedade de troca de arestas no topo da minha cabeça, embora eu ficaria surpreso se não existissem tais gráficos.