Gráfica de caminata regular

Gráfica matemática

En teoría de grafos , un grafo con recorrido regular es un grafo simple en el que el número de recorridos cerrados de cualquier longitud desde un vértice hasta sí mismo solo depende de la elección del vértice, pero no de ella. Los grafos con recorrido regular pueden considerarse como un análogo de la teoría de grafos espectrales de los grafos transitivos de vértices . Si bien un grafo con recorrido regular no es necesariamente muy simétrico , todos sus vértices se comportan de manera idéntica con respecto a las propiedades espectrales del grafo. ${\displaystyle \ell }$ ${\displaystyle \ell }$

Definiciones equivalentes

Supongamos que es un grafo simple. Sea la matriz de adyacencia de , el conjunto de vértices de , y el polinomio característico del subgrafo sin vértices para todos Entonces los siguientes son equivalentes: ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle G}$ ${\displaystyle V(G)}$ ${\displaystyle G}$ ${\displaystyle \Phi _{G-v}(x)}$ ${\displaystyle G-v}$ ${\displaystyle v\in V(G).}$

• ${\displaystyle G}$Es caminar regularmente.
• ${\displaystyle A^{k}}$es una matriz diagonal constante para todos ${\displaystyle k\geq 0.}$
• ${\displaystyle \Phi _{G-u}(x)=\Phi _{G-v}(x)}$a pesar de ${\displaystyle u,v\in V(G).}$

Ejemplos

• Los gráficos transitivos de vértice son regulares en su recorrido.
• Los gráficos semisimétricos son regulares. ^{[1] [ fuente no confiable ]}
• Los grafos regulares en cuanto a distancia son regulares en cuanto a recorrido. En términos más generales, cualquier grafo simple en un álgebra coherente homogénea es regular en cuanto a recorrido.
• Un gráfico regular conexo es regular si: ^{[ dudoso – discutir ] [ cita requerida ]}
  • Tiene como máximo cuatro valores propios distintos.
  • No tiene triángulos y tiene como máximo cinco valores propios distintos.
  • Es bipartito y tiene como máximo seis valores propios distintos.

Propiedades

• Un gráfico de caminata regular es necesariamente un gráfico regular.
• Los complementos de los gráficos de caminata regular son caminata regular.
• Los productos cartesianos de gráficos de recorrido regular son de recorrido regular.
• Los productos categóricos de gráficos de caminata regular son de caminata regular.
• Los productos fuertes de gráficos de caminata regular son de caminata regular.
• En general, el gráfico lineal de un gráfico de caminata regular no es de caminata regular.

a-Gráficos regulares de caminata

Un grafo es regular en recorridos si para cualesquiera dos vértices y de distancia como máximo el número de recorridos de longitud desde hasta depende únicamente de y . ^[2] ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle k,}$ ${\displaystyle \ell }$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle k}$ ${\displaystyle \ell }$

Porque estos son exactamente los gráficos de caminata regular. ${\displaystyle k=0}$

En analogía con los grafos de recorrido regular que generalizan grafos transitivos por vértices, los grafos de recorrido regular 1 pueden considerarse como grafos simétricos generalizadores , es decir, grafos que son transitivos por vértices y aristas. Por ejemplo, el grafo de Hoffman es de recorrido regular 1 pero no simétrico.

Si es al menos el diámetro del grafo, entonces los grafos regulares en el recorrido coinciden con los grafos regulares en la distancia . De hecho, si y el grafo tiene un valor propio de multiplicidad como máximo (excepto para los valores propios y , donde es el grado del grafo), entonces el grafo ya es regular en la distancia. ^[3] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k\geq 2}$ ${\displaystyle k}$ ${\displaystyle d}$ ${\displaystyle -d}$ ${\displaystyle d}$

Referencias

1. "¿Existen sólo un número finito de grafos cúbicos regulares que no son transitivos en cuanto a vértices ni regulares en cuanto a distancias?". mathoverflow.net . Consultado el 21 de julio de 2017 .
2. Cristina Dalfó, Miguel Angel Fiol y Ernest Garriga, "On -Walk-Regular Graphs", Electronic Journal of Combinatorics 16(1) (2009), artículo R47. ${\displaystyle k}$
3. Marc Camara et al., "Aspectos geométricos de gráficos regulares de 2 recorridos", Álgebra lineal y sus aplicaciones 439(9) (2013), 2692-2710.

Enlaces externos

• Chris Godsil y Brendan McKay , Condiciones de viabilidad para la existencia de gráficos de caminata regular.