Kirkland, Steve (2010) Algebraic Connectivity for Vertex-Deleted Subgraphs, and a Notion of Vertex Centrality. Discrete Mathematics, 310 (4). pp. 911-921. ISSN 0012-365X

Download (207kB)

Abstract

Let G be a connected graph, suppose that v is a vertex of G, and denote the subgraph formed from G by deleting vertex v by G\v. Denote the algebraic connectivities of G and G\v by α(G) and (G\v), respectively. In this paper, we consider the functions ∅(v) = α(G)− α(G\v) and k(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.

Item Type:	Article
Keywords:	Algebraic connectivity; Vertex-deleted subgraph; Vertex centrality; Hamilton Institute.
Academic Unit:	Faculty of Science and Engineering > Research Institutes > Hamilton Institute Faculty of Science and Engineering > Mathematics and Statistics
Item ID:	1894
Identification Number:	https://doi.org/10.1016/j.disc.2009.10.011
Depositing User:	Hamilton Editor
Date Deposited:	23 Mar 2010 10:06
Journal or Publication Title:	Discrete Mathematics
Publisher:	Elsevier BV, North-Holland
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads