Grafo vértice-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 vértice-transitivo é um grafo G tal que, dados quaisquer dois vértices v1 e v2 de G, existe algum automorfismo

f:V(G) \rightarrow V(G)\

tal que

f(v_1) = v_2.\

Em outras palavras, um grafo é vértice-transitivo se o seu grupo de automorfismo atua transitivamente em seus vértices.[1] Um grafo é vértice-transitivo se e somente se seu grafo complementar é, uma vez que as ações do grupo são idênticas.

Todo grafo simétrico, sem vértices isolados é vértice-transitivo, e cada grafo vértice-transitivo é regular. No entanto, nem todos os grafos vértice-transitivos são simétricos (por exemplo, as arestas do tetraedro truncado), e nem todos os grafos regulares são vértice-transitivos (por exemplo, o grafo de Frucht).

Exemplos finitos[editar | editar código-fonte]

As arestas do tetraedro truncado formam um grafo vértice-transitivo (também um grafo de Cayley) que não é simétrico.

Grafos vértice-transitivos finitos incluem os grafos simétricos (como o grafo de Petersen, o grafo de Heawood e os vértices e arestas dos sólidos platônicos). Os grafos de Cayley finitos (como ciclos de cubos conectados) também são vértice-transitivos, como o são os vértices e arestas dos sólidos de Arquimedes (embora apenas dois deles sejam simétricos).

Propriedades[editar | editar código-fonte]

A conectividade de arestas de um grafo vértice-transitivo é igual ao grau d, enquanto a conectividade de vértices será, no mínimo, 2(d+1)/3.[2] Se o grau é de 4 ou menos, ou o grafo também é aresta-transitivo, ou o grafo é um grafo de Cayley mínimo, então a conectividade de vértice também será igual a d.[3]

Exemplos infinitos[editar | editar código-fonte]

Grafos vértice-transitivos finitos incluem:

Dois grafos vértice-transitivos contáveis são chamados quase-isométricos se a razão de suas funções distância é delimitada a partir de baixo e de cima. Uma conjectura conhecida diz que todo grafo infinito vértice-transitivo é quase-isométrico a um grafo de Cayley. Um contra-exemplo foi proposto por Diestel e Leader.[4] Mais recentemente, Eskin, Fisher e Whyte confirmaram o contra-exemplo.[5]

Ver também[editar | editar código-fonte]

Referências

  1. Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, Graduate Texts in Mathematics, 207, New York: Springer-Verlag 
  2. Godsil, C. and Royle, G. (2001), Algebraic Graph Theory, Springer Verlag 
  3. Babai, L. (1996), Technical Report TR-94-10, University of Chicago [1]
  4. DIESTEL, Reinhard; LEADER, Imre. (2001). "A conjecture concerning a limit of non-Cayley graphs". Journal of Algebraic Combinatorics 14: 17–25. DOI:10.1023/A:1011257718029.
  5. Eskin, Alex; Fisher, David; Whyte, Kevin (2005), Quasi-isometries and rigidity of solvable groups, Arxiv