Grafo simétrico

O grafo de Petersen é um grafo (cúbico) simétrico. Qualquer par de vértices ligados pode ser mapeado para outro por um automorfismo, uma vez que qualquer anel de cinco vértices pode ser mapeado para qualquer outro.

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

Ligações externas

[biggs-1] ↑ ^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

[godsil-2] GODSIL, Chris; ROYLE, Gordon (2001). Algebraic Graph Theory. New York: Springer. p. 59. isbn 0-387-95220-9

[babai-3] 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

[4] BOUWER, Z. (1970). «Vertex and Edge Transitive, But Not 1-Transitive Graphs». Canad. Math. Bull. 13. pp. 231–237

[handbook-5] GROSS, J.L.; YELLEN, J. (2004). Handbook of Graph Theory. [S.l.]: CRC Press. p. 491. ISBN 1584880902

[6] 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 .

[7] Marston Conder, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput, vol. 20, pp. 41–63

[8] Foster, R. M. "Geometrical Circuits of Electrical Networks." Transactions of the American Institute of Electrical Engineers 51, 309–317, 1932.

[9] "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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

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		antissimétrico		assimétrico