A lower bound for algebraic connectivity based on the connection-graph-stability method

DOI10.1016/J.LAA.2010.12.019zbMATH Open1226.05146arXiv0909.2782OpenAlexW2064571435WikidataQ107438156 ScholiaQ107438156MaRDI QIDQ2431183FDOQ2431183

Authors: Ali Ajdari Rad, Mahdi Jalili, Martin Hasler 

Publication date: 11 April 2011

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: In this paper a tight lower bound for algebraic connectivity of graphs (second smallest eigenvalue of the Laplacian matrix of the graph) based on connection-graph-stability method is introduced. The connection-graph-stability score for each edge is defined as the sum of the length of all the shortest paths making use of that edge. We prove that the algebraic connectivity of the graph is lower bounded by the size of the graph divided by the maximum connection graph stability of the edges.

Full work available at URL: https://arxiv.org/abs/0909.2782

Recommendations

• scientific article; zbMATH DE number 7473309
• 2-connected graphs with the minimum algebraic connectivity
• The algebraic connectivity of graphs with given stability number
• A sharp upper bound on algebraic connectivity using domination number
• scientific article; zbMATH DE number 2246587

zbMATH Keywords

algebraic connectivitygraph Laplacianconnection-graph-stability score

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Connectivity (05C40)

Cites Work

• A faster algorithm for betweenness centrality*
• Title not available (Why is that?)
• Lower bounds of the Laplacian spectrum of graphs based on diameter
• Old and new results on algebraic connectivity of graphs
• Eigenvalues, diameter, and mean distance in graphs
• Connection graph stability method for synchronized coupled chaotic systems

Cited In (12)

• Lower bounds for the algebraic connectivity of graphs with specified subgraphs
• Efficient rewirings for enhancing synchronizability of dynamical networks
• A divide-and-conquer bound for aggregate's quality and algebraic connectivity
• Distributed algebraic connectivity estimation for undirected graphs with upper and lower bounds
• Some new lower bounds on the algebraic connectivity of graphs
• A lower bound for the algebraic connectivity of a graph in terms of the domination number
• Title not available (Why is that?)
• The vertex connectivity and the third largest eigenvalue in regular (multi-)graphs
• Weighted betweenness and algebraic connectivity
• Spectral bounds for the connectivity of regular graphs with given order
• Optimization of synchronizability in complex spatial networks
• Sharp spectral bounds for the edge-connectivity of regular graphs

This page was built for publication: A lower bound for algebraic connectivity based on the connection-graph-stability method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431183)