Measures of irregularity of graphs
AUTOR(ES)
Oliveira, Joelma Ananias de, Oliveira, Carla Silva, Justel, Claudia, Abreu, Nair Maria Maia de
FONTE
Pesqui. Oper.
DATA DE PUBLICAÇÃO
08/11/2013
RESUMO
A graph is regular if every vertex is of the same degree. Otherwise, it is an irregular graph. Although there is a vast literature devoted to regular graphs, only a few papers approach the irregular ones. We have found four distinct graph invariants used to measure the irregularity of a graph. All of them are determined through either the average or the variance of the vertex degrees. Among them there is the index of the graph, a spectral parameter, which is given as a function of the maximum eigenvalue of its adjacency matrix. In this paper, we survey these invariants with highlight to their respective properties, especially those relative to extremal graphs. Finally, we determine the maximum values of those measures and characterize their extremal graphs in some special classes.
