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, todos los vértices tienen el mismo grado o valencia. Un gráfico dirigido regular también debe satisfacer la condición más fuerte de que el grado de entrada y el de salida de cada vértice son iguales entre sí. [1] Un grafo regular con vértices de grado se llama ‑grafo regular o grafo regular de grado . Además, del lema del apretón de manos , un gráfico regular contiene un número par de vértices con grado impar.
Los gráficos regulares de grado máximo 2 son fáciles de clasificar: un gráfico 0-regular consta de vértices desconectados, un gráfico 1-regular consta de aristas desconectadas y un gráfico 2-regular consta de una unión disjunta de ciclos y cadenas infinitas.
Un grafo fuertemente regular es un grafo regular donde 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 gráficos más pequeños que son regulares pero no fuertemente regulares son el gráfico de ciclo y el gráfico circulante en 6 vértices.
El gráfico completo es fuertemente regular para cualquier .
Un teorema de Nash-Williams dice que todo gráfico regular de 2k + 1 vértices tiene un ciclo hamiltoniano .
Es bien sabido que las condiciones necesarias y suficientes para que exista un grafo regular de orden son que y que sea par.
