En teoría de grafos , un grafo muy irregular es un grafo en el que, para cada vértice, todos los vecinos de ese vértice tienen grados distintos .
Los gráficos irregulares fueron caracterizados inicialmente por Yousef Alavi , Gary Chartrand , Fan Chung , Paul Erdős , Ronald Graham y Ortrud Oellermann . [1] Estaban motivados para definir el 'opuesto' de un gráfico regular , un concepto que se ha estudiado a fondo y se ha entendido bien.
Definir un 'gráfico irregular' no fue inmediatamente obvio. En un gráfico 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 diferentes grados. Uno puede sentirse tentado a definir un gráfico irregular como si tuviera todos los vértices de distintos grados excepto dos, pero este tipo de gráficos también se entienden bien y, por lo tanto, no son interesantes. [2]
Así pues, los teóricos de grafos se volvieron hacia el tema 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 gráfico es, pues, localmente irregular si para cada vértice v de G los vecinos de v tienen grados distintos, y estos gráficos se denominan gráficos altamente irregulares. [1]
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 hay un grafo G que es r- regular y contiene H como subgrafo inducido. [3]
Las definiciones de irregularidad han sido importantes en el estudio de la heterogeneidad de las redes, lo que tiene implicaciones en las redes que se encuentran en la biología, la ecología, la tecnología y la economía. [4] Se han sugerido varias estadísticas de gráficos, muchas de las cuales se basan en la cantidad de vértices en un gráfico y sus grados. La caracterización de gráficos altamente irregulares también se ha aplicado a la cuestión de la heterogeneidad, pero ninguno de ellos arroja suficiente luz sobre las situaciones del mundo real. Se continúan realizando esfuerzos para encontrar formas apropiadas de cuantificar la heterogeneidad de la red. [4]