Gráfico regular

En teoría de grafos , un grafo regular es un grafo en el que cada vértice tiene el mismo número de vecinos; es decir, cada vértice tiene el mismo grado o valencia. Un grafo regular dirigido 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 denomina grafo k -regular o grafo regular de grado k .

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

Un gráfico 3-regular se conoce como gráfico cúbico .

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

El gráfico completo K _m es fuertemente regular para cualquier m .

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

Las condiciones necesarias y suficientes para que exista un grafo -regular de orden son que y que sea par. ${\displaystyle k}$ ${\displaystyle n}$${\displaystyle n\geq k+1}$${\displaystyle nk}$

Demostración: Un grafo completo tiene cada par de vértices distintos conectados entre sí por una única arista. Por lo tanto, las aristas son máximas en un grafo completo y el número de aristas es y el grado aquí es . Por lo tanto , . Este es el mínimo para un . Observe también que si cualquier grafo regular tiene orden , entonces el número de aristas es, por lo que tiene que ser par. En tal caso, es fácil construir grafos regulares considerando los parámetros apropiados para grafos circulantes . ${\displaystyle {\binom {n}{2}}={\dfrac {n(n-1)}{2}}}$${\displaystyle n-1}$${\displaystyle k=n-1,n=k+1}$${\displaystyle n}$${\displaystyle k}$${\displaystyle n}$${\displaystyle {\dfrac {nk}{2}}}$${\displaystyle nk}$

Del lema del apretón de manos , un grafo k -regular con k impar tiene un número par de vértices.

Un teorema de Nash-Williams dice que todo grafo k ‑regular en 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 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 , por lo que para tales vectores propios , tenemos . ${\displaystyle {\textbf {j}}=(1,\dots ,1)}$${\displaystyle {\textbf {j}}}$${\displaystyle v=(v_{1},\dots ,v_{n})}$${\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 dirección "solo si" es una consecuencia del teorema de Perron-Frobenius . ^[2]

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

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

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

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

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

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