Grafo aresta-transitivo
Famílias de grafos definidos por seus automorfismos | ||||
distância-transitivo | distância-regular | fortemente regular | ||
simétrico (arco-transitivo) | t-transitivo, t ≥ 2 | . | ||
(se conectado) | ||||
transitivo nos vértices e nas arestas | aresta-transitivo e regular | aresta-transitivo | ||
vértice-transitivo | regular | |||
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 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
Grafos aresta-transitivos incluem qualquer grafo bipartido completo , 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.