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 \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 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.. Handbook of Graph Theory. [S.l.]: CRC Press, 2004. p. 491. ISBN 1584880902
  2. BABAI, L.;GRAHAM, R. (ed.); GROETSCHEL, M.; LOVASZ, L.. Handbook of Combinatorics. [S.l.]: Elsevier, 1996.
  3. Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
  4. BIGGS, Norman. Algebraic Graph Theory. 2ª ed. Cambridge: Cambridge University Press, 1993. 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..