Title of article :
New measures of graph irregularity
Author/Authors :
Elphick, Clive University of Central Florida - Department of Electrical Engineering and Computer Science, USA , Wocjan, Pawel University of Central Florida - Department of Electrical Engineering and Computer Science, USA
Abstract :
In this paper, we define and compare three new measures of graph irregularity. We use these measures to tighten upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan’s theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.
Keywords :
graph irregularity , clique , chromatic number , Randic index , network heterogeneity
Journal title :
Electronic Journal of Graph Theory and Applications (EJGTA)
Journal title :
Electronic Journal of Graph Theory and Applications (EJGTA)
