Gráfico de distancia regular - Distance-regular graph

En matemáticas , un gráfico de distancia regular es un gráfico regular tal que para dos vértices cualesquiera v y w , el número de vértices a una distancia j de vy a una distancia k de w depende solo de j , k e i = d (v , w) .

Cada gráfico transitivo a la distancia es regular a la distancia. De hecho, los gráficos de distancia regular se introdujeron como una generalización combinatoria de los gráficos de distancia transitiva, que tienen las propiedades de regularidad numérica de estos últimos sin tener necesariamente un gran grupo de automorfismos .

Matrices de intersección

Resulta que una gráfica de diámetro es regular a la distancia si y solo si hay una matriz de enteros tal que para todos , da el número de vecinos de a distancia de y da el número de vecinos de a distancia de para cualquier par de vértices y a una distancia en . La matriz de números enteros que caracteriza a un gráfico de distancia regular se conoce como matriz de intersección . ${\ Displaystyle G}$${\ Displaystyle d}$${\ Displaystyle \ {b_ {0}, b_ {1}, \ ldots, b_ {d-1}; c_ {1}, \ ldots, c_ {d} \}}$${\ Displaystyle 1 \ leq j \ leq d}$${\ Displaystyle b_ {j}}$${\ Displaystyle u}$${\ Displaystyle j + 1}$${\ Displaystyle v}$${\ Displaystyle c_ {j}}$${\ Displaystyle u}$${\ Displaystyle j-1}$${\ Displaystyle v}$${\ Displaystyle u}$${\ Displaystyle v}$${\ Displaystyle j}$${\ Displaystyle G}$

Gráficos regulares de distancia cospectral

Un par de gráficos regulares de distancia conectados son cospectrales si y solo si tienen la misma matriz de intersección.

Un gráfico regular a distancia se desconecta si y solo si es una unión disjunta de gráficos regulares a distancia cospectral.

Propiedades

Supongamos que es un gráfico de valencia regular a distancia conectado con matriz de intersección . Para todos : dejar que denotan el gráfico -regular con matriz de adyacencia formado por relativa pares de vértices en a una distancia , y dejar que indican el número de vecinos de a una distancia de por cualquier par de vértices y a una distancia en . ${\ Displaystyle G}$ ${\ Displaystyle k}$${\ Displaystyle \ {b_ {0}, b_ {1}, \ ldots, b_ {d-1}; c_ {1}, \ ldots, c_ {d} \}}$${\ Displaystyle 0 \ leq j \ leq d}$${\ Displaystyle G_ {j}}$${\ Displaystyle k_ {j}}$ ${\ Displaystyle A_ {j}}$${\ Displaystyle G}$${\ Displaystyle j}$${\ Displaystyle a_ {j}}$${\ Displaystyle u}$${\ Displaystyle j}$${\ Displaystyle v}$${\ Displaystyle u}$${\ Displaystyle v}$${\ Displaystyle j}$${\ Displaystyle G}$

Propiedades de la teoría de grafos

• ${\ Displaystyle {\ frac {k_ {j + 1}} {k_ {j}}} = {\ frac {b_ {j}} {c_ {j + 1}}}}$ para todos . ${\ Displaystyle 0 \ leq j <d}$
• ${\ Displaystyle b_ {0}> b_ {1} \ geq \ cdots \ geq b_ {d-1}> 0}$ y . ${\ Displaystyle 1 = c_ {1} \ leq \ cdots \ leq c_ {d} \ leq b_ {0}}$

Propiedades espectrales

• ${\ Displaystyle k \ leq {\ frac {1} {2}} (m-1) (m + 2)}$ para cualquier multiplicidad de valores propios de , a menos que sea ​​un gráfico multipartito completo. ${\ Displaystyle m> 1}$${\ Displaystyle G}$${\ Displaystyle G}$
• ${\ Displaystyle d \ leq 3m-4}$ para cualquier multiplicidad de valores propios de , a menos que sea ​​un gráfico de ciclo o un gráfico multipartito completo. ${\ Displaystyle m> 1}$${\ Displaystyle G}$${\ Displaystyle G}$
• ${\ Displaystyle \ lambda \ in \ {\ pm k \}}$ si es un valor propio simple de . ${\ Displaystyle \ lambda}$${\ Displaystyle G}$
• ${\ Displaystyle G}$ tiene valores propios distintos. ${\ Displaystyle d + 1}$

Si es muy regular , entonces y . ${\ Displaystyle G}$${\ Displaystyle n \ leq 4m-1}$${\ Displaystyle k \ leq 2m-1}$

Ejemplos de

El gráfico de Klein de grado 7 y el mapa asociado incrustados en una superficie orientable del género 3. Este gráfico tiene una distancia regular con la matriz de intersección {7,4,1; 1,2,7} y el grupo de automorfismo PGL (2,7).

Algunos primeros ejemplos de gráficos de distancia regular incluyen:

• Los gráficos completos .
• Los gráficos de ciclos .
• Los gráficos impares .
• Los gráficos de Moore .
• Gráfico de colinealidad de un polígono cercano regular .
• El gráfico de Wells y el gráfico de Sylvester .
• Gráficos de diámetro muy regulares . ${\ Displaystyle 2}$

Clasificación de gráficos de distancia regular

Solo hay un número finito de gráficos de distancia regular conectados distintos de cualquier valencia dada . ${\ Displaystyle k> 2}$

De manera similar, solo hay un número finito de gráficos regulares de distancia conectados distintos con cualquier multiplicidad de valor propio dada (con la excepción de los gráficos multipartitos completos). ${\ Displaystyle m> 2}$

Gráficos regulares de distancia cúbica

Los gráficos regulares de distancia cúbica se han clasificado completamente.

Las 13 gráficas cúbicas regulares de distancia distintas son K ₄ (o gráfica tetraédrica ), K _3,3 , la gráfica de Petersen , la gráfica cúbica , la gráfica de Heawood , la gráfica de Pappus , la gráfica de Coxeter , la gráfica de Tutte-Coxeter , la gráfica dodecaédrica gráfico , el gráfico Desargues , Tutte 12-jaula , el gráfico Biggs-Smith , y el gráfico de Foster .

Referencias

Otras lecturas

• Godsil, C. D. (1993). Combinatoria algebraica . Serie de matemáticas de Chapman y Hall. Nueva York: Chapman y Hall. págs. xvi + 362. ISBN   978-0-412-04131-0 . Señor   1220704 .