Grafo distância-transitivo

Grafo distância-transitivo

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		antissimétrico		assimétrico

No campo da matemática da teoria dos grafos, um grafo distância-transitivo é um grafo tal que, dados dois vértices quaisquer v e w em qualquer distância i, e quaisquer outros dois vértices x e y à mesma distância, há um automorfismo do grafo que carrega v para x e w para y.

Um grafo distância-transitivo é vértice-transitivo e simétrico bem como distância-regular.

Um grafo distância-transitivo é interessante, em parte, porque tem um grande grupo de automorfismo. Alguns exemplos interessantes de grupos finitos são os grupos de automorfismos de grafos distância-transitivos, especialmente daqueles cujo diâmetro é de 2.

Grafos distância-transitivos foram definidos primeiramente em 1971 por Norman L. Biggs e D. H. Smith, que mostraram que existem apenas 12 grafos distância-transitivos trivalentes finitos. São eles:

Nome do grafo	Contagem de vértices	Diâmetro	Cintura	array de interseção
grafo completo K4	4	1	3	{3;1}
grafo bipartido completo K3,3	6	2	4	{3,2;1,3}
grafo de Petersen	10	2	5	{3,2;1,1}
grafo do cubo	8	3	4	{3,2,1;1,2,3}
grafo de Heawood	14	3	6	{3,2,2;1,1,3}
grafo de Papo	18	4	6	{3,2,2,1;1,1,2,3}
grafo de Coxeter	28	4	7	{3,2,2,1;1,1,1,2}
grafo de Tutte–Coxeter	30	4	8	{3,2,2,2;1,1,1,3}
grafo do dodecaedro	20	5	5	{3,2,1,1,1;1,1,1,2,3}
grafo de Desargues	20	5	6	{3,2,2,1,1;1,1,2,2,3}
grafo de Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
grafo de Foster	90	8	10	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}

Independente em 1969, um grupo de russos liderados por Georgy Adelson-Velsky mostrou que existem grafos que são distância-regulares, mas não distância-transitivos. O único grafo deste tipo com um grau três é o Tutte 12-gaiola de 126 vértices. O menor grafo distância-regular que não é a distância-transitivo é o grafo de Shrikhande. Listas completas de grafos distância-transitivos são conhecidas para alguns graus maiores do que três, mas a classificação de grafos distância-transitivos com graus de vértice arbitrariamente grandes continua em aberto.

A mais simples família de exemplos assintótica de grafos distância-transitivos são os grafos Hipercubo. Outras famílias são os grafos cubo dobrado e os grafos torre quadrados. Todas essas três famílias têm arbitrariamente um grau elevado.

Referências

Primeiros trabalhos

• Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; Faradžev, I. A. (1969), «An example of a graph which has no transitive group of automorphisms», Doklady Akademii Nauk SSSR, 185: 975–976, MR0244107 .

• Biggs, Norman (1971), «Intersection matrices for linear graphs», Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23, MR0285421 .

• Biggs, Norman (1971), Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series, 6, London & New York: Cambridge University Press, MR0327563 .

• Biggs, N. L.; Smith, D. H. (1971), «On trivalent graphs», Bulletin of the London Mathematical Society, 3: 155–158, doi:10.1112/blms/3.2.155, MR0286693 .

• Smith, D. H. (1971), «Primitive and imprimitive graphs», The Quarterly Journal of Mathematics, Oxford, Second Series, 22: 551–557, doi:10.1093/qmath/22.4.551, MR0327584 .

Pesquisas

• Biggs, N. L. (1993), «Distance-Transitive Graphs», Algebraic Graph Theory 2nd ed. , Cambridge University Press, pp. 155–163 , chapter 20.

• Van Bon, John (2007), «Finite primitive distance-transitive graphs», European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014, MR2287450 .

• Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), «Distance-Transitive Graphs», Distance-Regular Graphs, New York: Springer-Verlag, pp. 214–234 , chapter 7.

• Cohen, A. M. Cohen (2004), «Distance-transitive graphs», in: Beineke, L. W.; Wilson, R. J., Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, 102, Cambridge University Press, pp. 222–249 .

• Godsil, C.; Royle, G. (2001), «Distance-Transitive Graphs», Algebraic Graph Theory, New York: Springer-Verlag, pp. 66–69 , section 4.5.

• Ivanov, A. A. (1992), «Distance-transitive graphs and their classification», in: Faradžev, I. A.; Ivanov, A. A.; Klin, M.; Woldar, A. J., The Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Series), 84, Dordrecht: Kluwer, pp. 283–378, MR1321634 .