Extremal Properties of Graphs and Eigencentrality in Trees with a Given Degree Sequence

Abstract

In this article, we investigate several issues related to the use of the index , known as the Zagreb index (see Gutman and Das, 2004) or “S-metric” (Alderson and Li, 2007). We present some new upper and lower bounds for S(G), in terms of the degree sequence of G. Then, we concentrate on trees and prove that in trees with maximum S(G) the eigenvector ordering is coherent with the degree ordering; that is, degree central vertices are also eigenvector central. This confirms results given in Bonacich (2007). Further, we show that these trees have minimum diameter and maximum spectral radius in the set of trees with a given degree sequence. A simple application to a company organizational network is provided.

Keywords:

• bounds
• degree sequence
• diameter
• eigenvector centrality
• spectral radius
• trees

View correction statement:

Corrigendum

ACKNOWLEDGMENTS

We thank the two anonymous referees for their suggestions and comments that improved substantially the quality of this article. We also thank Giovanni Zambruno for his careful reading and helpful suggestions.

Notes

¹For α = 0 the index simply counts (twice) the edges of G.

²In Li et al. (2005b) it is stressed that r(G) and S(G) are “normalized against a different background set of graphs …. S(G) is constrained to simple and connected graphs, whereas r(G) involves no such constraints” (p. 486). In Alderson and Li (2007) it is added that “r(G) does a relatively poor job of distinguishing among graphs having the same degree sequence, particularly when the degree sequence shows high variability” (p. 5).

³The rearrangement inequality (see Hardy, Littlewood, and Pólya, 1988) states that if x ₁ ≥ x ₂ ≥…≥x _n and y ₁ ≥ y ₂ ≥…≥y _n are real numbers, then for any permutation of x ₁, x ₂,…, x _n , we have .

⁴Notice that in this case d ₁ > 2 and d ₂ = 2.