Saltar para o conteúdo

Grafo meio-transitivo

Origem: Wikipédia, a enciclopédia livre.
Famílias de grafos definidos por seus automorfismos
distância-transitivodistância-regularfortemente regular
simétrico (arco-transitivo)t-transitivo, t ≥ 2.

(se conectado)
transitivo nos vértices e nas arestasaresta-transitivo e regulararesta-transitivo
vértice-transitivoregular
grafo de Cayleyantissimétricoassimétrico


No campo da matemática da teoria dos grafos, um grafo meio-transitivo é um grafo que é tanto vértice-transitivo quanto aresta-transitivo, mas não é simétrico.[1] Em outras palavras, um grafo é meio-transitivo, se o seu grupo de automorfismo atua transitivamente em ambos os seus vértices e arestas, mas não em pares ordenados de vértices ligados.

O grafo de Holt é o menor grafo meio-transitivo. A falta de simetria reflexiva neste desenho destaca o fato de que as arestas não são equivalentes aos suas inversas.

Todo grafo simétrico conectado deve ser vértice-transitivo e aresta-transitivo, e o inverso é verdadeiro para grafos de grau ímpar,[2] de modo que os grafos meio-transitivos de grau ímpar não existem. Contudo, existem grafos meio-transitivos de grau par.[3] O menor grafo meio-transitivo é o grafo de Holt, com grau 4 e 27 vértices.[4][5]

Referências

  1. GROSS, J.L. and Yellen, J. (2004). Handbook of Graph Theory. [S.l.]: CRC Press. p. 491. ISBN 1584880902 
  2. BABAI, L.;GRAHAM, R. (ed.); GROETSCHEL, M.; LOVASZ, L. (1996). «Automorphism groups, isomorphism, reconstruction». Handbook of Combinatorics. [S.l.]: Elsevier. Consultado em 11 de outubro de 2010. Arquivado do original em 11 de junho de 2010 
  3. Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
  4. BIGGS, Norman (1993). Algebraic Graph Theory 2ª ed. Cambridge: Cambridge University Press. ISBN 0-521-45897-8 
  5. HOLT, Derek F. (1981). «A graph which is edge transitive but not arc transitive». Journal of Graph Theory. 5 (2): 201–204. doi:10.1002/jgt.3190050210 .