PROFILPELAJAR.COM

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 u₁—v₁ e u₂—v₂ de G , há um automorfismo

f : V(G) → V(G)

tal que

f(u₁) = u₂ and f(v₁) = v₂.^[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 u₁ e u₂), 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

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