On Vertex Connectivity and Absolute Algebraic Connectivity for Graphs

DOI10.1080/03081080290025453MaRDI QIDQ3147574zbMATH OpenOpenAlexFDO

Authors S. J. Kirkland, S. Pati

Publication date 14 January 2003

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL http://taylorandfrancis.metapress.com/openurl.asp?genre=article&issn=0308-1087&volume=50&issue=3&spage=253

zbMATH Keywords

absolute algebraic connectivityvertex connectivityweighted graphweighted Laplacian matrix

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42)

Review text

Given a graph \(G=(V,E)\), its absolute algebraic connectivity is defined as the supremum of the second smallest eigenvalue of its weighted Laplacian matrix \(L_w\) over the set of all nonnegative edge-weightings \(w\) satisfying \(\sum_{(i,j)\in E} w_{ij}=|E|\). The authors find an attainable upper bound on the absolute algebraic connectivity of all graphs with a given number of vertices \(n\) and a given vertex connectivity \(v\), \(1\leq v\leq n-2\), and provide examples of graphs for which this bound is attained.

Recommendations

• Extremizing algebraic connectivity subject to graph theoretic constraints
• Algebraic connectivity and disjoint vertex subsets of graphs
• scientific article; zbMATH DE number 7473309
• On graphs with equal algebraic and vertex connectivity
• A bound on the algebraic connectivity of a graph in terms of the number of cutpoints

Cites work

• Absolute algebraic connectivity of trees
• Laplacian matrices of graphs: A survey
• On graphs with equal algebraic and vertex connectivity

Cited in

(11)

• Some minimax problems for graphs
• Algebraic connectivity and disjoint vertex subsets of graphs
• On algebraic connectivity of graphs with at most two points of articulation in each block
• scientific article; zbMATH DE number 2246587 (Why is no real title available?)
• ON THE ALGEBRAIC EMBEDDABILITY IN THE CLASS OF FUNCTIONS POSSESSING CONNECTED GRAPHS
• On graphs with equal algebraic and vertex connectivity
• Conjectures on index and algebraic connectivity of graphs
• Upper bounds on algebraic connectivity via convex optimization
• Old and new results on algebraic connectivity of graphs
• Absolute algebraic connectivity of double brooms and trees
• Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality

This page was built for publication: On Vertex Connectivity and Absolute Algebraic Connectivity for Graphs

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