MURAL - Maynooth University Research Archive Library

    Algebraic Connectivity for Vertex-Deleted Subgraphs, and a Notion of Vertex Centrality

    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

    [img] Download (207kB)
    Official URL:

    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...

    Add this article to your Mendeley library


    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:
    Depositing User: Hamilton Editor
    Date Deposited: 23 Mar 2010 10:06
    Journal or Publication Title: Discrete Mathematics
    Publisher: Elsevier BV, North-Holland
    Refereed: Yes
    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)

    View Item Item control page


    Downloads per month over past year

    Origin of downloads