Grafo meio-transitivo

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.

Famílias de grafos definidos por seus automorfismos
distância-transitivo	${\displaystyle \rightarrow }$	distância-regular	${\displaystyle \leftarrow }$	fortemente regular
${\displaystyle \downarrow }$
simétrico (arco-transitivo)	${\displaystyle \leftarrow }$	t-transitivo, t ≥ 2		.
${\displaystyle \downarrow }$ (se conectado)
transitivo nos vértices e nas arestas	${\displaystyle \rightarrow }$	aresta-transitivo e regular	${\displaystyle \rightarrow }$	aresta-transitivo
${\displaystyle \downarrow }$		${\displaystyle \downarrow }$
vértice-transitivo	${\displaystyle \rightarrow }$	regular
${\displaystyle \uparrow }$
grafo de Cayley		antissimétrico		assimétrico

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 !CS1 manut: Nomes múltiplos: lista de autores (link)
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 !CS1 manut: Nomes múltiplos: lista de autores (link)
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.