Degree heterogeneity of graphs and networks. II. Comparison with other indices

Abstract

We prove a few analytical results showing the relation of degree heterogeneity index to the number of pendant nodes, and to some irregularity indices proposed in the literature. We show evidences supporting the fact that other indices described in the literature do not measure the degree heterogeneity of a graph and illustrate how some of them fails in recognize important aspects of this structural property of networks. For instance, we prove here that large Cayley trees are regular-like only when the degree of nonpendant nodes is relatively small. On the contrary, these graphs are very heterogeneous resembling more star graphs than regular ones.

Subject Classification:

• 05C82
• 05C07
• 05C50
• 05C75

Keywords:

• Degree heterogeneity
• Degree distributions
• Laplacian matrices
• Cayley trees
• synchroniz-ability
• Complex networks