Grafo aresta-transitivo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Famílias de grafos definidos por seus automorfismos
distância-transitivo \rightarrow distância-regular \leftarrow fortemente regular
\downarrow
simétrico (arco-transitivo) \leftarrow t-transitivo, t ≥ 2 .
\downarrow
(se conectado)
transitivo nos vértices e nas arestas \rightarrow aresta-transitivo e regular \rightarrow aresta-transitivo
\downarrow \downarrow
vértice-transitivo \rightarrow regular
\uparrow
grafo de Cayley anti-simétrico assimétrico


No campo da matemática da teoria dos grafos, um grafo aresta-transitivo é um grafo G tal que, dadas duas arestas e1 e e2 de G, há um automorfismo de G que mapeia e1 em e2.[1]

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

Exemplos e propriedades[editar | editar código-fonte]

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

Grafos aresta-transitivos incluem qualquer grafo bipartido completo K_{m,n}, e qualquer grafo simétrico, como os vértices e as arestas do cubo.[1] Grafos simétricos são també 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é é regular, mas não vértice-transitivo, é chamado semi-simétrico. O grafo Gray mais uma vez dá um exemplo.

Referências

  1. a b c Biggs, Norman. Algebraic Graph Theory. 2ª ed. Cambridge: Cambridge University Press, 1993. 118 p. ISBN 0-521-45897-8