Grafo meio-transitivo

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Famílias de grafos definidos por seus automorfismos
distância-transitivo distância-regular fortemente regular
simétrico (arco-transitivo) t-transitivo, t ≥ 2 .

(se conectado)
transitivo nos vértices e nas arestas aresta-transitivo e regular aresta-transitivo
vértice-transitivo regular
grafo de Cayley anti-simétrico assimé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 CRC Press [S.l.] p. 491. ISBN 1584880902. 
  2. BABAI, L.;GRAHAM, R. (ed.); GROETSCHEL, M.; LOVASZ, L. (1996). «Automorphism groups, isomorphism, reconstruction». Handbook of Combinatorics Elsevier [S.l.] 
  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..