Computing tight upper bounds on the algebraic connectivity of certain graphs

DOI10.1016/J.LAA.2008.08.018MaRDI QIDQ958040zbMATH OpenOpenAlexFDO

Authors Oscar Rojo

Publication date 2 December 2008

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

Full work available at URL https://doi.org/10.1016/j.laa.2008.08.018

zbMATH Keywords

algebraic connectivityBethe treesgeneralized Bethe treesLaplacian matrix

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48)

Recommendations

• Tight bounds on the algebraic connectivity of Bethe trees
• Spectra of copies of a generalized Bethe tree attached to any graph
• The spectra of a graph obtained from copies of a generalized Bethe tree
• scientific article; zbMATH DE number 7473309
• Spectra of weighted generalized Bethe trees joined at the root

Cites work

• Eigenvalues, diameter, and mean distance in graphs
• scientific article; zbMATH DE number 4213315 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• Old and new results on algebraic connectivity of graphs
• On the spectra of certain rooted trees
• Spectra of weighted generalized Bethe trees joined at the root
• The Laplacian Spectrum of a Graph
• The spectra of a graph obtained from copies of a generalized Bethe tree
• The spectra of some trees and bounds for the largest eigenvalue of any tree
• The spectra of the adjacency matrix and Laplacian matrix for some balanced trees
• Theory of monomer-dimer systems
• Tight bounds on the algebraic connectivity of a balanced binary tree
• Tight bounds on the algebraic connectivity of Bethe trees

Cited in

(13)

• Spectra of copies of a generalized Bethe tree attached to any graph
• Distributed algebraic connectivity estimation for undirected graphs with upper and lower bounds
• An upper bound on the algebraic connectivity of outerplanar graphs
• The sharpness of a lower bound on the algebraic connectivity for maximal graphs
• An upper bound on algebraic connectivity of graphs with many cutpoints
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• Extremizing algebraic connectivity subject to graph theoretic constraints
• On a bound on algebraic connectivity: the case of equality
• Computing Vertex Connectivity: New Bounds from Old Techniques
• scientific article; zbMATH DE number 7473309 (Why is no real title available?)
• Lower bounds for the algebraic connectivity of graphs with specified subgraphs
• Complexity of deciding connectivity in real algebraic sets
• Tight bounds on the algebraic connectivity of Bethe trees

This page was built for publication: Computing tight upper bounds on the algebraic connectivity of certain graphs

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