Grafo simétrico
No campo da matemática da teoria dos grafos, um grafo G é simétrico (ou arco-transitivo) se, dados quaisquer dois pares de vértices ligados u1—v1 e u2—v2 de G , há um automorfismo
- f : V(G) → V(G)
tal que
- f(u1) = u2 and f(v1) = v2.[1]
Em outras palavras, um grafo é simétrico se seu grupo de automorfismo age transitivamente em pares ordenados de vértices ligados (isto é, sobre as arestas consideradas como tendo um sentido).[2] Tal grafo é chamado às vezes também 1-arco-transitivo[2] ou flag-transitivo.[3]
Por definição (ignorando u1 e u2), um grafo simétrico sem vértices isolados deve também ser vértice-transitivo.[1] Como a definição acima mapeia uma aresta a outra, um grafo simétrico também deve ser aresta-transitivo. Contudo, um grafo aresta-transitivo não precisa ser simétrico, uma vez que a—b pode mapear a c—d, mas não a d—c. Grafos simétricos, por exemplo, aão aresta-transitivos e regulares, mas não vértice-transitivos.
Todo grafo simétrico conexo deve, portanto, ser tanto vértice-transitivo quanto aresta-transitivo, e o inverso é verdadeiro para grafos de grau ímpar.[3] No entanto, para graus pares, existem grafos conectados que são vértice-transitivos e aresta-transitivos, mas não simétricos.[4] Tais grafos são denominados meio-transitivos.[5] O menor grafo conexo meio-transitiva é o grafo de Holt, com grau 4 e 27 vértices.[1][6] De forma confusa, alguns autores usam o termo "grafo simétrico" para significar um grafo que é vértice-transitivo e aresta-transitivo, ao invés de um grafo arco-transitivo. Tal definição inclui grafos meio-transitivos, que são excluídos pela definição acima.
Um grafo distância-transitivo é aquele em que em vez de considerar pares de vértices ligados (i.e. vértices a uma distância de um), a definição abrange dois pares de vértices, cada um à mesma distância. Tais grafos são automaticamente simétricos, por definição.[1]
Um t-arco é definido como uma sequência de t+1 vértices ligados, com quaisquer vértices repetidos estando a mais de 2 passos distante. Um grafo t-transitivo é um grafo tal que o grupo de automorfismo atua transitivamente nos t-arcos, mas não nos (t+1)-arcos. Uma vez que os 1-arcos são simplesmente arestas, qualquer grafo simétrico de grau 3 ou superior tem que ser t-transitivo para algum t, e o valor de t pode ser usado para além disso classificar grafos simétricos. O cubo é 2-transitivo, por exemplo.[1]
Exemplos editar
Combinando a condição de simetria com a restrição de que os grafos sejam cúbicos (ou seja, todos os vértices tem grau 3) resulta abolutamente uma forte condição, e tais grafos são raros o bastante para serem citados. O censo de Foster e suas extensões fornecem tais listas.[7] O censo de Foster foi iniciado na década de 1930 por Ronald M. Foster enquanto ele era um contratado pela Bell Labs,[8] e em 1988 (quando Foster estava com 92 anos de idade[1]) o então censo de Foster corrente (listando todos os grafos cúbicos simétricos até 512 vértices) foi publicado em forma de livro.[9]
Referências
- ↑ a b c d e f BIGGS, Norman (1993). Algebraic Graph Theory 2ª ed. Cambridge: Cambridge University Press. p. 118–140. ISBN 0-521-45897-8
- ↑ a b GODSIL, Chris; ROYLE, Gordon (2001). Algebraic Graph Theory. New York: Springer. p. 59. isbn 0-387-95220-9
- ↑ a b BABAI, L.; GRAHAM, R. (ed.); GROETSCHEL, M.(ed.); LOVASZ, L.(ed.) (1996). «Automorphism groups, isomorphism, reconstruction». Handbook of Combinatorics. [S.l.]: Elsevier. Consultado em 12 de outubro de 2010. Arquivado do original em 11 de junho de 2010
- ↑ BOUWER, Z. (1970). «Vertex and Edge Transitive, But Not 1-Transitive Graphs». Canad. Math. Bull. 13. pp. 231–237
- ↑ GROSS, J.L.; YELLEN, J. (2004). Handbook of Graph Theory. [S.l.]: CRC Press. p. 491. ISBN 1584880902
- ↑ HOLT, Derek F. (1981). «A graph which is edge transitive but not arc transitive». Journal of Graph Theory. 5 (2). pp. 201–204. doi:10.1002/jgt.3190050210.
- ↑ Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63
- ↑ Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.
- ↑ "The Foster Census: R.M. Foster's Census of Connected Symmetric Trivalent Graphs", by Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson and Z. Star (1988) ISBN 0919611192