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

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