Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality

摘要

Let G be a connected graph, suppose that nu is a vertex of G, and denote the subgraph formed from G by deleting vertex nu by Gu. Denote the algebraic connectivities of G and Gu by alpha (G) and alpha(Gu), respectively. In this paper, we consider the functions phi(nu) = alpha(G) - alpha(Gu) and kappa(v) = alpha(Gu)/alpha(G), provide attainable upper and lower bounds on both functions, and characterise the equality cases in those bounds. The function kappa yields a measure of vertex centrality, and we apply that measure to analyse certain graphs arising from food webs.