Grafo vértice-transitivo

Famílias de grafos definidos por seus automorfismos
distância-transitivo	${\displaystyle \rightarrow }$	distância-regular	${\displaystyle \leftarrow }$	fortemente regular
${\displaystyle \downarrow }$
simétrico (arco-transitivo)	${\displaystyle \leftarrow }$	t-transitivo, t ≥ 2		.
${\displaystyle \downarrow }$ (se conectado)
transitivo nos vértices e nas arestas	${\displaystyle \rightarrow }$	aresta-transitivo e regular	${\displaystyle \rightarrow }$	aresta-transitivo
${\displaystyle \downarrow }$		${\displaystyle \downarrow }$
vértice-transitivo	${\displaystyle \rightarrow }$	regular
${\displaystyle \uparrow }$
grafo de Cayley		antissimétrico		assimétrico

No campo da matemática da teoria dos grafos, um grafo vértice-transitivo é um grafo G tal que, dados quaisquer dois vértices v₁ e v₂ de G, existe algum automorfismo

${\displaystyle f:V(G)\rightarrow V(G)\ }$

tal que

${\displaystyle f(v_{1})=v_{2}.\ }$

Em outras palavras, um grafo é vértice-transitivo se o seu grupo de automorfismo atua transitivamente em seus vértices.^[1] Um grafo é vértice-transitivo se e somente se seu grafo complementar é, uma vez que as ações do grupo são idênticas.

Todo grafo simétrico, sem vértices isolados é vértice-transitivo, e cada grafo vértice-transitivo é regular. No entanto, nem todos os grafos vértice-transitivos são simétricos (por exemplo, as arestas do tetraedro truncado), e nem todos os grafos regulares são vértice-transitivos (por exemplo, o grafo de Frucht).

Grafos vértice-transitivos finitos incluem os grafos simétricos (como o grafo de Petersen, o grafo de Heawood e os vértices e arestas dos sólidos platônicos). Os grafos de Cayley finitos (como ciclos de cubos conectados) também são vértice-transitivos, como o são os vértices e arestas dos sólidos de Arquimedes (embora apenas dois deles sejam simétricos).

A conectividade de arestas de um grafo vértice-transitivo é igual ao grau d, enquanto a conectividade de vértices será, no mínimo, 2(d+1)/3.^[2] Se o grau é de 4 ou menos, ou o grafo também é aresta-transitivo, ou o grafo é um grafo de Cayley mínimo, então a conectividade de vértice também será igual a d.^[3]

Grafos vértice-transitivos finitos incluem:

• Caminhos infinitos (infinitos em ambas as direções);
• Árvores regulares infinitas, por exemplo o grafo de Cayley dos grupos livres;
• Grafos de Cayley infinitos;
• O grafo de Rado.

Dois grafos vértice-transitivos contáveis são chamados quase-isométricos se a razão de suas funções distância é delimitada a partir de baixo e de cima. Uma conjectura conhecida diz que todo grafo infinito vértice-transitivo é quase-isométrico a um grafo de Cayley. Um contra-exemplo foi proposto por Diestel e Leader.^[4] Mais recentemente, Eskin, Fisher e Whyte confirmaram o contra-exemplo.^[5]

• grafo aresta-transitivo
• grafo semi-simétrico

Referências