En teoría de grafos , un grafo altamente irregular es un grafo en el que, para cada vértice, todos los vecinos de ese vértice tienen grados distintos .
Los grafos irregulares fueron caracterizados inicialmente por Yousef Alavi , Gary Chartrand , Fan Chung , Paul Erdős , Ronald Graham y Ortrud Oellermann . [1] Ellos se sintieron motivados a definir el "opuesto" de un grafo regular , un concepto que ha sido estudiado a fondo y bien comprendido.
La definición de un "grafo irregular" no fue inmediatamente obvia. En un grafo k -regular, todos los vértices tienen grado k . En cualquier grafo G con más de un vértice, dos vértices en G deben tener el mismo grado, por lo que un grafo irregular no puede definirse como un grafo con todos los vértices de grados diferentes. Uno puede verse tentado entonces a definir un grafo irregular como aquel que tiene todos los vértices de grados distintos excepto dos, pero estos tipos de grafos también se entienden bien y por lo tanto no son interesantes. [2]
Los teóricos de grafos se centraron entonces en la cuestión de la regularidad local. Un grafo es localmente regular en un vértice v si todos los vértices adyacentes a v tienen grado r . Un grafo es localmente irregular si para cada vértice v de G los vecinos de v tienen grados distintos, y estos grafos se denominan grafos altamente irregulares. [1]
Algunos datos sobre gráficos altamente irregulares descritos por Alavi et al.: [ 3]
Esta última observación puede considerarse análoga a un resultado de Dénes Kőnig , que establece que si H es un grafo con mayor grado r , entonces existe un grafo G que es r -regular y contiene a H como un subgrafo inducido. [3]
Las definiciones de irregularidad han sido importantes en el estudio de la heterogeneidad de redes, lo que tiene implicaciones en redes que se encuentran en biología, ecología, tecnología y economía. [4] Se han sugerido varias estadísticas de grafos, muchas de las cuales se basan en el número de vértices de un grafo y sus grados. La caracterización de grafos altamente irregulares también se ha aplicado a la cuestión de la heterogeneidad, pero ninguna de ellas arroja suficiente luz sobre situaciones del mundo real. Se siguen realizando esfuerzos para encontrar formas apropiadas de cuantificar la heterogeneidad de las redes. [4]