Grafo aresta-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 aresta-transitivo é um grafo G tal que, dadas duas arestas e₁ e e₂ de G, há um automorfismo de G que mapeia e₁ em e₂.[1]

Em outras palavras, um grafo é aresta-transitivo, se o seu grupo de automorfismo atua transitivamente em suas arestas.

Exemplos e propriedades

O grafo Gray é aresta-transitivo e regular, mas não é vértice-transitivo.

Grafos aresta-transitivos incluem qualquer grafo bipartido completo ${\displaystyle K_{m,n}}$, e qualquer grafo simétrico, como os vértices e as arestas do cubo.[1] Grafos simétricos são também vértice-transitivo (se eles são conectados), mas no geral grafos aresta-transitivos não precisam ser vértice-transitivos. O grafo Gray é um exemplo de um grafo que é aresta-transitivo, mas não vértice-transitivo. Todos estes grafos são bipartidos,[1] e, portanto, podem ser coloridos, com apenas duas cores.

Um grafo aresta-transitivo que também é regular, mas não vértice-transitivo, é chamado semi-simétrico. O grafo Gray mais uma vez dá um exemplo.

Referências

1. Biggs, Norman (1993). Algebraic Graph Theory 2ª ed. Cambridge: Cambridge University Press. 118 páginas. ISBN 0-521-45897-8