Graph irregularity: Discussion, graph extensions and new proposals

Abstract

Este artículo presenta un análisis de las medidas de irregularidad de grafos que se encuentran en la literatura. Desde su discusión dos puntos importantes aparecen: primero, la ausencia de relación entre todos ellos, sino una sola excepción - con las estructuras de los grafos correspondientes y, además, sus valores extremales conocidos corresponden a grafos que tienen secuencias de grados con pocos valores diferentes. Se proponen dos nuevas medidas, tratando de cumplir con estos puntos. Sus valores se calculan para grafos extremales asociados con otras medidas y para grafos antiregulares. Por último, se determinan los gráficos de quartiles o boxplots de todas estas medidas, para algunos conjuntos de grafos de la literatura y para cuatro conjuntos donde las secuencias ordenadas de grados son constantes. Todas las medidas estudiadas tienen complejidad polinómica.

Keywords

• grafos
• irregularidad
• medidas de irregularidad
• extensiones de grafos