Grafo meio-transitivo
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 | antissimé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.
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
- ↑ GROSS, J.L. and Yellen, J. (2004). Handbook of Graph Theory. [S.l.]: CRC Press. p. 491. ISBN 1584880902 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ 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 !CS1 manut: Nomes múltiplos: lista de autores (link)
- ↑ Bouwer, Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231–237, 1970.
- ↑ BIGGS, Norman (1993). Algebraic Graph Theory 2ª ed. Cambridge: Cambridge University Press. ISBN 0-521-45897-8
- ↑ 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 .