En matemáticas , una gráfica de distancia regular es una gráfica 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) .
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
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 distancia si y solo si hay una matriz de números 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 distancia en . La matriz de números enteros que caracteriza a un gráfico de distancia regular se conoce como matriz de intersección .
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
Suponer es una gráfica de valencia regular a distancia conectada con matriz de intersección . Para todos: dejar denotar el -Gráfico regular con matriz de adyacencia formado relacionando pares de vértices en a distancia , y deja denotar el número de vecinos de a distancia de para cualquier par de vértices y a distancia en .
Propiedades de la teoría de grafos
- para todos .
- y .
Propiedades espectrales
- para cualquier multiplicidad de valores propios de , a no ser que es un gráfico multipartito completo.
- para cualquier multiplicidad de valores propios de , a no ser que es un gráfico de ciclo o un gráfico multipartito completo.
- Si es un valor propio simple de .
- posee valores propios distintos.
Si es muy regular , entonces y .
Ejemplos de
Algunos primeros ejemplos de gráficos de distancia regular incluyen:
- Los gráficos completos .
- Los ciclos de gráficos .
- 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 .
Clasificación de gráficos de distancia regular
Solo hay un número finito de gráficos regulares de distancia conectados distintos de cualquier valencia dada . [1]
De manera similar, solo hay un número finito de gráficos regulares de distancia conectados distintos con cualquier multiplicidad de valor propio dada [2] (a excepción de los gráficos multipartitos completos).
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 4 (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
- ^ Bang, S .; Dubickas, A .; Koolen, JH; Moulton, V. (10 de enero de 2015). "Hay sólo un número finito de gráficos de distancia regular de valencia fija mayor que dos". Avances en Matemáticas . 269 (Suplemento C): 1–55. arXiv : 0909.5253 . doi : 10.1016 / j.aim.2014.09.025 . S2CID 18869283 .
- ^ Godsil, CD (1 de diciembre de 1988). "Delimitación del diámetro de los gráficos de distancia regular". Combinatorica . 8 (4): 333–343. doi : 10.1007 / BF02189090 . ISSN 0209-9683 . S2CID 206813795 .
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 .