Gráfico regular

En teoría de grafos , un grafo regular es un grafo donde cada vértice tiene el mismo número de vecinos; es decir, cada vértice tiene el mismo grado o valencia. Un grafo dirigido regular también debe satisfacer la condición más fuerte de que el grado de entrada y el grado de salida de cada vértice interno sean iguales entre sí. ^{[ 1 ]} Un grafo regular con vértices de grado k se llama grafo k -regular o grafo regular de grado k .

Los grafos regulares de grado como máximo 2 son fáciles de clasificar: un grafo 0-regular consta de vértices desconectados, un grafo 1-regular consta de aristas desconectadas y un grafo 2-regular consta de una unión disjunta de ciclos y cadenas infinitas.

De forma análoga a la terminología de los polinomios de bajo grado, un grafo 3-regular o 4-regular se denomina a menudo grafo cúbico o grafo cuártico , respectivamente. Del mismo modo, es posible denotar los grafos k -regulares con${\displaystyle k=5,6,7,8,\ldots }$como quíntico, séptico, óctico , etcétera  .

Un grafo fuertemente regular es aquel en el que cada par de vértices adyacentes tiene en común el mismo número l de vecinos, y cada par de vértices no adyacentes tiene en común el mismo número n de vecinos. Los grafos más pequeños que son regulares pero no fuertemente regulares son el grafo cíclico y el grafo circulante de 6 vértices.

El grafo completo K _m es fuertemente regular para cualquier m .

• 
  Gráfico 0-regular
• 
  1-gráfico regular
• 
  grafo 2-regular
• 
  Gráfico 3-regular

Según la fórmula de suma de grados , un grafo k -regular con n vértices tiene${\displaystyle {\frac {nk}{2}}}$bordes. En particular, al menos uno de los órdenes n y el grado k debe ser un número par.

Un teorema de Nash-Williams dice que todo grafo k -regular con 2 k + 1 vértices tiene un ciclo hamiltoniano .

Sea A la matriz de adyacencia de un grafo. Entonces el grafo es regular si y solo si${\displaystyle {\textbf {j}}=(1,\dots,1)}$es un vector propio de A. ^{[ 2} ] Su valor propio será el grado constante del grafo. Los vectores propios correspondientes a otros ^valores propios son ortogonales a${\displaystyle {\textbf {j}}}$, por lo tanto, para tales autovectores${\displaystyle v=(v_{1},\dots,v_{n})}$, tenemos${\displaystyle \sum _{i=1}^{n}v_{i}=0}$.

Un grafo regular de grado k es conexo si y solo si el valor propio k tiene multiplicidad uno. La condición "solo si" es una consecuencia del teorema de Perron-Frobenius . ^{[ 2 ]}

También existe un criterio para grafos regulares y conexos  : un grafo es conexo y regular si y solo si la matriz de unos J , con${\displaystyle J_{ij}=1}$, está en el álgebra de adyacencia del grafo (lo que significa que es una combinación lineal de potencias de A ). ^{[ 3 ]}

Sea G un grafo k -regular con diámetro D y valores propios de la matriz de adyacencia.${\displaystyle k=\lambda _ {0}>\lambda _ {1}\geq \cdots \geq \lambda _ {n-1}}$. Si G no es bipartito, entonces

${\displaystyle D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.}$^{[ 4 ]}

Existe un${\displaystyle k}$-grafo regular de orden${\displaystyle n}$si y solo si los números naturales n y k satisfacen la desigualdad${\displaystyle n\geq k+1}$y eso${\displaystyle nk}$es par.

Prueba : Si un grafo con n vértices es k- regular, entonces el grado k de cualquier vértice v no puede exceder el número${\displaystyle n-1}$de vértices distintos de v , y de hecho al menos uno de n y k debe ser par, por lo que también lo es su producto.

Por el contrario, si n y k son dos números naturales que satisfacen tanto la desigualdad como la condición de paridad, entonces sí existe un grafo circulante k -regular.${\displaystyle C_{n}^{s_{1},\ldots ,s_{r}}}$de orden n (donde el${\displaystyle s_{i}}$denotan los "saltos" mínimos tales que los vértices con índices que difieren en un${\displaystyle s_{i}}$son adyacentes). Si además k es par, entonces${\displaystyle k=2r}$y una posible opción es${\displaystyle (s_{1},\ldots ,s_{r})=(1,2,\ldots ,r)}$. De lo contrario, k es impar, por lo que n debe ser par, digamos con${\displaystyle n=2m}$, y luego${\displaystyle k=2r-1}$y los 'saltos' pueden ser elegidos como${\displaystyle (s_{1},\ldots ,s_{r})=(1,2,\ldots ,r-1,m)}$.

Si${\displaystyle n=k+1}$, entonces este grafo circulante está completo .

Existen algoritmos rápidos para generar, salvo isomorfismo, todos los grafos regulares con un grado y número de vértices dados. ^{[ 5 ]}

• grafo regular aleatorio
• Grafo fuertemente regular
• Gráfico de Moore
• Gráfico de jaula
• Gráfico altamente irregular

• Weisstein, Eric W. "Grafo regular" . MathWorld .
• Weisstein, Eric W. "Grafo fuertemente regular" . MathWorld .
• Software y datos de GenReg , por Markus Meringer.
• Nash-Williams, Crispin (1969), Secuencias de valencia que obligan a los grafos a tener circuitos hamiltonianos , Informe de investigación de la Universidad de Waterloo, Waterloo, Ontario: Universidad de Waterloo