Measures of irregularity of graphs
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.
| Main Authors: | , , , |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Pesquisa Operacional
2013
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382013000300004 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|