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

DOI10.1016/J.LAA.2010.12.019MaRDI QIDQ2431183zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3681933 (Why is no real title available?)
• A faster algorithm for betweenness centrality*
• Connection graph stability method for synchronized coupled chaotic systems
• Eigenvalues, diameter, and mean distance in graphs
• Lower bounds of the Laplacian spectrum of graphs based on diameter
• Old and new results on algebraic connectivity of graphs

Cited in

(12)

• Lower bounds for the algebraic connectivity of graphs with specified subgraphs
• A divide-and-conquer bound for aggregate's quality and algebraic connectivity
• Efficient rewirings for enhancing synchronizability of dynamical networks
• 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
• scientific article; zbMATH DE number 5942896 (Why is no real title available?)
• 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)