Gráfico regular

Gráfico donde cada vértice tiene el mismo número de vecinos

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 .

Casos especiales

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 .

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

Existencia

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}$

Propiedades

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]

Generación

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

Véase también

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

Referencias

1. Chen, Wai-Kai (1997). Teoría de grafos y sus aplicaciones en ingeniería . World Scientific. pp. 29. ISBN 978-981-02-1859-1.
2. Cvetković, DM; Doob, M.; y Sachs, H. Espectros de grafos: teoría y aplicaciones, 3.ª ed. enl. rev. Nueva York: Wiley, 1998.
3. Curtin, Brian (2005), "Caracterizaciones algebraicas de condiciones de regularidad de grafos", Diseños, códigos y criptografía , 34 (2–3): 241–248, doi :10.1007/s10623-004-4857-4, MR  2128333.
4. [1] ^{[ cita requerida ]}
5. Meringer, Markus (1999). "Generación rápida de grafos regulares y construcción de jaulas" (PDF) . Journal of Graph Theory . 30 (2): 137–146. doi :10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.

Enlaces externos

• Weisstein, Eric W. "Gráfico regular". MathWorld .
• 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