New measures of graph irregularity

DOI10.5614/EJGTA.2014.2.1.5MaRDI QIDQ5177034zbMATH OpenOpenAlexFDO

Authors Clive Elphick, Pawel Wocjan

Publication date 5 March 2015

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://arxiv.org/abs/1305.3570

zbMATH Keywords

chromatic numbercliquegraph irregularitynetwork heterogeneityRandić index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Abstract: In this paper, we define and compare four new measures of graph irregularity. We use these measures to prove 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.

Recommendations

• Irregularidad de grafos: Discusión, extensiones de grafos y nuevas propuestas
• A note on the irregularity of graphs
• Graphs with maximal irregularity
• scientific article; zbMATH DE number 1409213
• On the irregularity of graphs based on the arithmetic-geometric mean inequality

Cited in

(13)

• Propagation of mean degrees
• Graph irregularity and its measures
• On the upper bounds for the degree deviation of graphs
• Stepwise irregular graphs
• Irregularidad de grafos: Discusión, extensiones de grafos y nuevas propuestas
• Note on irregular graphs
• scientific article; zbMATH DE number 7413770 (Why is no real title available?)
• Exhaustive and metaheuristic exploration of two new structural irregularity measures
• Classifying Inconsistency Measures Using Graphs
• A unified framework for the expander mixing lemma for irregular graphs and its applications
• The reciprocal irregularity of a graph
• Geometric and topological properties of fractal networks
• Some properties of stepwise irregular graphs

This page was built for publication: New measures of graph irregularity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5177034)