Gráfico transitivo de distancia

Un gráfico de distancia transitiva es un gráfico en el que cualquier par ordenado de vértices se traduce en cualquier otro par ordenado de vértices con la misma distancia entre vértices por uno de los automorfismos del gráfico .

Un concepto cercano es un gráfico de distancia regular , pero su naturaleza es diferente. Si un gráfico de distancia transitiva se define a partir de la simetría del gráfico a través de la condición de automorfismo, entonces un gráfico de distancia regular se define a partir de la condición de su regularidad combinatoria. Cada gráfico de distancia transitiva es distancia regular, pero lo contrario no es cierto. Esto se demostró en 1969, incluso antes de que se acuñara el término "gráfico transitivo de distancia".

Los gráficos regulares de distancia de grados menores de 13 están completamente clasificados.

Definiciones de un gráfico transitivo de distancia

Hay varias definiciones diferentes en forma, pero idénticas en significado, de un gráfico transitivo de distancia. Se supone que el grafo es no dirigido, conexo y acotado. La definición utiliza los conceptos de distancia entre vértices de gráficos y automorfismo de gráficos : ${\ estilo de visualización \ Gamma = (V, E)}$

La distancia entre dos vértices de un gráfico es el número de aristas a lo largo del camino más corto que conecta y ${\ estilo de visualización d (u, v)}$ ${\ estilo de visualización u, v \ en V (\ Gamma)}$ ${\ estilo de visualización \ Gamma = (V, E)}$ $tu$ $v$
Un automorfismo de gráfico es un mapeo uno a uno del conjunto de vértices de un gráfico sobre sí mismo, conservando la adyacencia de los vértices. ${\ estilo de visualización g: V \ flecha derecha V}$
Un grupo de automorfismos de gráficos es un conjunto de automorfismos de gráficos. ${\ estilo de visualización \ mathrm {Aut} (\ Gamma)}$

Definición de Godzilla-Royle [1] Se dice que un grafo acotado, conectado y no dirigido es transitivo en distancia si para cualesquiera dos pares ordenados de sus vértices y tal que existe un automorfismo del grafo tal que

{\ estilo de visualización \ Gamma = (V, E)}

(u,v)

(x,y)

{\ estilo de visualización d (u, v) = d (x, y)}

gramo

\Gama

{\ estilo de visualización g: (u, v) \ flecha derecha (x, y)}

Definición de Biggs [2] [3] Sea un grafo no dirigido, conexo y acotado que tenga un grupo de automorfismos . Se dice que un grafo es transitivo en distancia si para todos los vértices tales que , existe un automorfismo , que mapea y

{\ estilo de visualización \ Gamma = (V, E)}

{\ estilo de visualización \ mathrm {Aut} (\ Gamma)}

\Gama

{\ estilo de visualización u, v, x, y}

{\ estilo de visualización d (u, v) = d (x, y)}

g\in g

{\ estilo de visualización u \ flecha derecha x}

{\ estilo de visualización v \ flecha derecha y}

Definición según Ivanov-Ivanov-Faradzhev [4] Se dice que un gráfico finito conectado no dirigido sin bucles y múltiples aristas es transitivo en distancia si su grupo de automorfismos actúa transitivamente en pares ordenados de vértices equidistantes

{\ estilo de visualización \ Gamma = (V, E)}

{\ estilo de visualización \ mathrm {Aut} (\ Gamma)}

Definición según Cowan [5] Sea un gráfico de diámetro conexo y sea su grupo de automorfismos. es transitiva en distancia si es transitiva en todo conjunto , donde . Un grafo es transitivo en distancia si su grupo de automorfismos es transitivo en distancia.

{\ estilo de visualización \ Gamma = (V, E)}

D

{\ estilo de visualización \ mathrm {Aut} (\ Gamma)}

{\ estilo de visualización \ mathrm {Aut} (\ Gamma)}

\Gama

{\displaystyle \Gamma _{i}=\left\{(x,y)\in \Gamma \times \Gamma :d(x,y)=i\right\))

i=0,\,1,\,\ldots,\,D

\Gama

{\ estilo de visualización \ mathrm {Aut} (\ Gamma)}

Definición según Ivanov [6] Sea un grafo no dirigido, conexo y acotado que tenga un grupo de automorfismos . Sea un subgrupo . Un grafo se llama -distancia -transitivo si por cada cuatro vértices tal que , hay un automorfismo que mapea y . Un grafo se llama transitivo de distancia si es transitivo de distancia para algún subgrupo del grupo de automorfismos del grafo.

{\ estilo de visualización \ Gamma = (V, E)}

{\ estilo de visualización \ mathrm {Aut} (\ Gamma)}

GRAMO

{\ estilo de visualización \ mathrm {Aut} (\ Gamma)}

\Gama

GRAMO

GRAMO

{\ estilo de visualización u, v, x, y}

{\ estilo de visualización d (u, v) = d (x, y)}

g\in g

{\ estilo de visualización u \ flecha derecha x}

{\ estilo de visualización v \ flecha derecha y}

GRAMO

GRAMO

En otras palabras, hay un gráfico transitivo de distancia si el subgrupo actúa transitivamente en el conjunto para cada .

\Gama

GRAMO

GRAMO

{\displaystyle \left\{(x,y)\mid x,e\in V(\Gamma ),\,d(x,y)=i\right\))

i

Matriz de intersecciones

Sea un grafo no dirigido, conexo y acotado, y dos de sus vértices estén separados entre sí. Todos los vértices incidentes al vértice se pueden dividir en tres conjuntos , y dependiendo de su distancia al vértice : ${\ estilo de visualización \ Gamma = (V, E)}$ ${\ estilo de visualización u, v \ en V (\ Gamma)}$ ${\ estilo de visualización j = d (u, v)}$ $w$ $tu$ $A$ $B$ $C$ ${\ estilo de visualización d (v, w)}$ $v$

{\displaystyle \left\{w\in A\dos puntos d(v,w)=j\right\))

, , .

{\displaystyle \left\{w\in B\colon d(v,w)=j+1\right\))

{\displaystyle \left\{w\in C\dos puntos d(v,w)=j-1\right\))

Si el gráfico es distancia-transitivo, entonces las potencias (números cardinales) de los conjuntos no dependen de los vértices , sino que dependen solo de la distancia y se denominan números de intersección . $\Gama$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $tú, v$ ${\ estilo de visualización j = d (u, v)}$

Conjunto de números de intersección

\iota (\Gamma )={\begin{Bmatrix}\ast &c_{1}&c_{2}&\dots &c_{d-1}&c_{d}\\a_{0}&a_{1}&a_ {2}&\puntos &a_{d-1}&a_{d}\\b_{0}&b_{1}&b_{2}&\puntos &b_{d-1}&\ast \\\end{Bmatriz}}

se llama matriz de intersección de un gráfico transitivo de distancia [7] [8] .

Propiedades

Cada gráfico transitivo de distancia es regular de distancia , pero lo contrario no es cierto [4] [9] [10] [11] .
Un gráfico transitivo de distancia es transitivo de vértice y simétrico [3] .
Una matriz de intersecciones de un gráfico de distancia regular de grado $k$ . Dado que el gráfico de distancia transitiva es regular, los números de intersección y . Además, . Por lo tanto, la matriz de intersección de un gráfico de distancia regular se puede escribir como [4] [7] [8] : $b_{0}=k$ $c_{1}=1$ $a_{i}+b_{i}+c_{i}=k$

\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2 },\,\puntos,\,c_{d}\end{Bmatriz}}

Ejemplos

Los ejemplos más simples de gráficos transitivos de distancia [5] [12] [13] :

gráficos completos $K_n$
grafos bipartitos completos (bicliques) con partes iguales $K_{{n,n}}$
gráficos de hipercubo $Q_{n}$

Ejemplos más complejos de gráficos transitivos de distancia:

Conde Johnson [14]
Gráfico de Grassmann [15]
conde de Hamming [16] [17]
Conde de Livingston [18]

Gráficos distancia-regulares y distancia-transitivos

A primera vista, un gráfico de distancia transitiva y un gráfico de distancia regular son conceptos muy cercanos. De hecho, todo grafo transitivo de distancia es regular en distancia. Sin embargo, su naturaleza es diferente. Si un gráfico de distancia transitiva se define en función de la simetría del gráfico a través de la condición de automorfismo, entonces un gráfico de distancia regular se define a partir de la condición de su regularidad combinatoria [19] .

Un grafo transitivo de distancia es transitivo de vértice y los números de intersección se definen para él . Para un gráfico de distancia regular, los números de intersección también se definen en términos de regularidad combinatoria. La distancia-transitividad de un gráfico implica su distancia-regularidad, pero lo contrario no es cierto [10] . Esto se demostró en 1969, incluso antes de la introducción del término "gráfico transitivo de distancia", por un grupo de matemáticos soviéticos ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [20] [10] . El gráfico de distancia regular más pequeño que no es transitivo de distancia es el gráfico de Shrikhande . El único gráfico trivalente de este tipo es el de 12 celdas de Tatta , un gráfico con 126 vértices [10] .

Clasificación de grafos transitivos de distancia

El primer resultado general en la clasificación de grafos distancia-transitivos fue obtenido por Biggs y Smith [21] en 1971, donde se clasificaron grafos de grado tres. Durante los próximos diez a quince años, el problema central en el estudio de grafos distancia-transitivos fue la clasificación de grafos distancia-transitivos de pequeños grados [22] . Los gráficos transitivos de distancia de grado cuatro fueron completamente clasificados por Smith [23] [24] .

En 1983 Cameron, Prager, Saxl y Seitz [25] e independientemente en 1985 Weiss [26] probaron que para cualquier potencia mayor que dos hay un número limitado de grafos transitivos de distancia [27] .

Clasificación de grafos transitivos de distancia cúbica

En 1971, N. Biggs y D. Smith demostraron el teorema de que entre los gráficos cúbicos (trivalentes) hay exactamente 12 gráficos transitivos de distancia [21] :

nombre del conteo	Número de vértices	Diámetro	Circunferencia	Matriz de intersección
Gráfico completo K 4	cuatro	una	3	{3;1}
Gráfico bipartito completo K 3,3	6	2	cuatro	{3,2;1,3}
Gráfico de hipercubo $Q_{3}$	ocho	3	cuatro	{3,2,1;1,2,3}
Conde de Petersen	diez	2	5	{3,2;1,1}
Conde de Heawood	catorce	3	6	{3,2,2;1,1,3}
Conde papá	Dieciocho	cuatro	6	{3,2,2,1;1,1,2,3}
gráfico de dodecaedro	veinte	5	5	{3,2,1,1,1;1,1,1,2,3}
Conde Desargués	veinte	5	6	{3,2,2,1,1;1,1,2,2,3}
Conde de Coxeter	28	cuatro	7	{3,2,2,1;1,1,1,2}
Conde de Thatta-Coxeter	treinta	cuatro	ocho	{3,2,2,2;1,1,1,3}
Conde de Foster	90	ocho	diez	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
Conde de Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Gráficos distancia-transitivos de grado mayor que tres

Todos los gráficos de grados transitivos de distancia son conocidos [28] . Todos los gráficos transitivos de distancia de grado (valencia) cuatro ( ) fueron obtenidos por D. Smith en 1973-74 [23] [24] , y los grados quinto, sexto y séptimo en 1984 por A. A. Ivanov, A. V. Ivanov e I. A. Faradzhev [ 29] . ${\ estilo de visualización k <13}$ $k=4$

En 1986, A. A. Ivanov y A. V. Ivanov obtuvieron todos los gráficos transitivos de distancia de grados de a [30] . ${\ estilo de visualización k = 8}$ ${\ estilo de visualización k = 13}$

Aproximaciones a la clasificación

Se obtuvieron listas de grafos distancia-transitivos de pequeños grados en el marco de un enfoque basado en considerar el estabilizador de un solo vértice y teoremas que limitan el diámetro del gráfico. A. A. Ivanov llamó a este enfoque "local". El enfoque "global" se basa en considerar la acción del grupo de automorfismos sobre el conjunto de vértices. Este enfoque permite clasificar grafos transitivos de distancia en los que la acción de un grupo es primitiva. A partir de ellos, luego se construyen todos los demás [22] .

Notas

↑ Godsil y Royle, 2001 , pág. 66.
↑ Biggs, 1971 , pág. 87.
↑ 1 2 Biggs, 1993 , pág. 118.
↑ 1 2 3 Ivanov, Ivanov y Faradzhev, 1984 , p. 1704.
↑ 12 Cohen , 2004 , pág. 223.
↑ Ivanov, 1994 , pág. 285.
↑ 1 2 Lauri y Scapelatto, 2016 , p. 33.
↑ 1 2 Biggs, 1993 , pág. 157.
↑ Lauri y Scapelatto, 2016 , pág. 34.
↑ 1 2 3 4 Brouwer, Cohen y Neumaier, 1989 , p. 136.
↑ Cohen, 2004 , pág. 232.
↑ Godsil y Royle, 2001 , pág. 66-67.
↑ Biggs, 1993 , pág. 158.
↑ Brouwer, Cohen y Neumaier 1989 , p. 255.
↑ Brouwer, Cohen y Neumaier 1989 , p. 269.
↑ Van Bon, 2007 , pág. 519.
↑ Brouwer, Cohen y Neumaier 1989 , p. 261.
↑ Weisstein, Eric W. Livingstone Graph en el sitio web de Wolfram MathWorld .
↑ Biggs, 1993 , pág. 159.
↑ Adelson-Velsky, Weisfeler, Leman y Faradzhev, 1969 .
↑ 12 Biggs y Smith, 1971 .
↑ 1 2 Ivanov, 1994 , págs. 288-292.
↑ 12 Smith , 1973 .
↑ 12 Smith , 1974 .
↑ Cameron PJ, Praeger CE, Saxl J. y Seitz GM Sobre la conjetura de Sims y los gráficos de distancia transitiva // Bull. Matemáticas de Londres. soc. - 1983. - vol. 15.- Pág. 499-506.
↑ Weiss R. Sobre gráficos transitivos de distancia // Bull. Matemáticas de Londres. soc. - 1985. - vol. 17.- Pág. 253-256.
↑ Brouwer, Cohen y Neumaier 1989 , p. 214.
↑ Brouwer, Cohen y Neumaier 1989 , p. 221-225.
↑ Ivanov, Ivanov y Faradzhev, 1984 .
↑ Ivanov e Ivanov, 1988 .

Literatura

Libros

Biggs N. Gráficos transitivos de distancia // Grupos finitos de automorfismos (ing.) . - Londres y Nueva York: Cambridge University Press, 1971. - vol. 6.- Pág. 86-96. - (Serie de notas de conferencias de la Sociedad Matemática de Londres).

Gráficos transitivos de distancia de Biggs NL // Teoría de gráficos algebraicos (inglés) . — 2ª edición. - Cambridge University Press, 1993. - P. 155-163. — 205p.

Brouwer AE, Cohen AM, Neumaier A. Distancia - Gráficos transitivos // Distancia-Gráficos regulares . - Nueva York: Springer-Verlag, 1989. - Págs. 214-234.

Cohen AM Gráficos transitivos de distancia // Temas de teoría de gráficos algebraicos / editado por LW Beineke, RJ Wilson. - Prensa de la Universidad de Cambridge, 2004. - Vol. 102. - Pág. 222-249. - (Enciclopedia de las Matemáticas y sus Aplicaciones).

Godsil C., Royle G. Gráficos transitivos de distancia // Teoría de gráficos algebraicos (inglés) . - Nueva York: Springer-Verlag, 2001. - vol. 207. - Pág. 66-69. — (Textos de Posgrado en Matemáticas). -doi : 10.1007 / 978-1-4613-0163-9 .
Ivanov AA, Ivanov AV Gráficos transitivos de distancia de valencia k , 8 < k < 13 // Combinatoria algebraica, extrema y métrica 1986 (inglés) / Deza, M., Frankl, P. y Rosenberg, I. (Eds. ) . - Cambridge: Cambridge University Press, 1988. - P. 112-145. - (Serie de notas de conferencias de la Sociedad Matemática de Londres). -doi : 10.1017 / CBO9780511758881 .

Ivanov AA Gráficos transitivos de distancia y su clasificación (inglés) // Faradžev IA, Ivanov AA, Klin MH, Woldar AJ (eds.) Investigaciones en teoría algebraica de objetos combinatorios. Matemáticas y sus aplicaciones (serie soviética). - Dordrecht: Springer , 1994. - vol. 84 . - pág. 283-378 . -doi : 10.1007 / 978-94-017-1972-8 .
Lauri J. , Scapelatto R. Temas en automorfismos y reconstrucción de grafos . — 2ª edición. - Cambridge: Cambridge University Press, 2016. - 188 p. - (Serie de notas de conferencias de la Sociedad Matemática de Londres). -doi : 10.1017/ CBO9781316669846 .

Artículos

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. En un ejemplo de un gráfico que no tiene un grupo de automorfismo transitivo // Informes de la Academia de Ciencias . - 1969. - T. 185 , N º 5 . - S. 975-976 .
Ivanov A. A., Ivanov A. V., Faradzhev I. A. Gráficos transitivos de distancia de grado 5, 6 y 7 // Zh. Vychisl. Matemáticas. y estera físico _ - 1984. - T. 24 , N º 11 . - S. 1704-1718 .
Biggs NL, Smith DH Sobre gráficos trivalentes // Boletín de la London Mathematical Society. - 1971. - vol. 3 , edición. 2 . - P. 155-158 . -doi : 10.1112 / blms/3.2.155 .
Smith DH Sobre gráficos tetravalentes // J. Lodon Math. soc. - 1973. - vol. 6 _ - Pág. 659-662 .
Smith DH Gráficos transitivos de distancia de valencia cuatro // J. Lodon Math. soc. - 1974. - vol. 8 _ - P. 377-384 .
Van Bon J. Gráficos transitivos de distancia primitivos finitos (inglés) // European Journal of Combinatorics. - 2007. - vol. 28 , edición. 2 . - Pág. 517-532 . -doi : 10.1016/ j.ejc.2005.04.014 .

Enlaces

Weisstein, Eric W. Distance-Transitive Graph (inglés) en el sitio web de Wolfram MathWorld .