Old and new results on algebraic connectivity of graphs

DOI10.1016/J.LAA.2006.08.017MaRDI QIDQ876302zbMATH OpenOpenAlexWikidataFDO

Authors Nair Abreu

Publication date 18 April 2007

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

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

zbMATH Keywords

bounds for the algebraic connectivityextremal graphsFiedler vectorsLaplacian integral graphsLaplacian of graphlimit pointsvertex and edge connectivities

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Recommendations

• Some new lower bounds on the algebraic connectivity of graphs
• A conjecture on algebraic connectivity of graphs
• On the \(d\)-dimensional algebraic connectivity of graphs
• Bounds on the algebraic connectivity of graphs
• A Note on an Old-Fashioned Algebra for (Disconnected) Graphs
• scientific article; zbMATH DE number 7473309
• New conjectures on algebraic connectivity and the Laplacian spread of graphs
• On Vertex Connectivity and Absolute Algebraic Connectivity for Graphs
• The algebraic connectivity of graphs under perturbation
• scientific article; zbMATH DE number 1135782

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A bound on the algebraic connectivity of a graph in terms of the number of cutpoints
• A note on limit points for algebraic connectivity
• A survey of graph laplacians
• Absolute algebraic connectivity of trees
• Algebraic connectivity of weighted trees under perturbation
• An upper bound on algebraic connectivity of graphs with many cutpoints
• An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
• Characteristic vertices of trees^*
• Completion of Laplacian integral graphs via edge addition
• Degree maximal graphs are Laplacian integral
• Eigenspaces of graphs
• Eigenvalues and expanders
• Eigenvalues, diameter, and mean distance in graphs
• Eigenvectors of acyclic matrices
• Extremizing algebraic connectivity subject to graph theoretic constraints
• Handbook of Graph Theory
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 4063128 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 3465473 (Why is no real title available?)
• scientific article; zbMATH DE number 3627232 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 2170331 (Why is no real title available?)
• scientific article; zbMATH DE number 4114654 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 4193718 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• scientific article; zbMATH DE number 2246587 (Why is no real title available?)
• Isomorph-Free Exhaustive Generation
• Laplace eigenvalues of graphs---a survey
• Laplacian graph eigenvectors
• Laplacian integral graphs in S(a, b)
• Laplacian matrices of graphs: A survey
• Lower bounds for the eigenvalues of Laplacian matrices
• Maximizing Algebraic Connectivity Over Unicyclic Graphs
• Minimizing algebraic connectivity over connected graphs with fixed girth
• On a bound on algebraic connectivity: the case of equality
• On algebraic connectivity and spectral integral variations of graphs
• On graphs with algebraic connectivity equal to minimum edge density
• On graphs with equal algebraic and vertex connectivity
• On the algebraic connectivity of graphs as a function of genus
• On the two conjectures of Graffiti
• On Vertex Connectivity and Absolute Algebraic Connectivity for Graphs
• Open problems of Paul Erd�s in graph theory
• Optimal linear labelings and eigenvalues of graphs
• Ordering trees by algebraic connectivity
• Parallel concepts in graph theory
• Parameters of connectivity in ()-linear graphs
• Recent results in the theory of graph spectra
• Some minimax problems for graphs
• The asymptotic behaviour of Fiedler's algebraic connectivity for random graphs
• The Laplacian Spectrum of a Graph
• The limit points of Laplacian spectra of graphs
• Tight bounds on the algebraic connectivity of a balanced binary tree
• Tight bounds on the algebraic connectivity of Bethe trees
• Transportation in graphs and the admittance spectrum
• Upper bounds on algebraic connectivity via convex optimization
• Variable neighborhood search for extremal graphs. I: The AutoGraphiX system
• Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures

Cited in

(only showing first 100 items - show all)

• Algebraic connectivity and doubly stochastic tree matrices
• The Laplacian spectral radius of tricyclic graphs with n vertices and k pendant vertices
• Ordering trees by the Laplacian coefficients
• On the algebraic connectivity of some caterpillars: a sharp upper bound and a total ordering
• Eigenvalues and edge-connectivity of regular graphs
• The asymptotic behaviour of Fiedler's algebraic connectivity for random graphs
• A note on limit points for algebraic connectivity
• Sixty years of network reliability
• A lower bound for the algebraic connectivity of a graph in terms of the domination number
• A new method optimizing the subgraph centrality of large networks
• Augmenting the algebraic connectivity for certain families of graphs
• Spectral and structural properties of random interdependent networks
• Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity
• New bounds for the signless Laplacian spread
• Synchronization in large-scale nonlinear network systems with uncertain links
• On algebraic connectivity and spectral integral variations of graphs
• On algebraic connectivity of directed scale-free networks
• An interlacing technique for spectra of random walks and its application to finite percolation clusters
• A tight upper bound on the spectral radius of bottleneck matrices for graphs
• A divide-and-conquer bound for aggregate's quality and algebraic connectivity
• Potential energy principles in networked systems and their connections to optimization problems on graphs
• Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods
• Improving connectivity of compromised digital networks via algebraic connectivity maximisation
• Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems
• Signless Laplacian spectral characterization of some disjoint union of graphs
• Laplacian spectrum of comaximal graph of the ring \(\mathbb{Z}_n\)
• A new approach based on spectral graph theory to avoiding enclosed holes in topology optimization
• On (distance) signless Laplacian spectra of graphs
• New conjectures on algebraic connectivity and the Laplacian spread of graphs
• Maxima of the Laplacian spectral radius of (minimally) 2-connected graphs with fixed size
• Algebraic connectivity and disjoint vertex subsets of graphs
• On synchronization in heterogeneous FitzHugh-Nagumo networks
• On trees with algebraic connectivity greater than or equal to \(2(1-\cos(\frac{\pi}{7}))\)
• Hubs-biased resistance distances on graphs and networks
• Ordering trees and graphs with few cycles by algebraic connectivity
• Maximizing algebraic connectivity for certain families of graphs
• Decentralized local-global connectivity maintenance for networked robotic teams
• Controllability-Gramian submatrices for a network consensus model
• Stability analysis and output-feedback synthesis of hybrid systems affected by piecewise constant parameters via dynamic resetting scalings
• `Hubs-repelling' Laplacian and related diffusion on graphs/networks
• Spectra of graphs resulting from various graph operations and products: a survey
• Addressing the envelope reduction of sparse matrices using a genetic programming system
• Consensus dynamics on random rectangular graphs
• Sign-changing diagonal perturbations of Laplacian matrices of graphs
• Algebraic connectivity of network-of-networks having a graph product structure
• Schur reduction of trees and extremal entries of the Fiedler vector
• Tighter spectral bounds for the cut size, based on Laplacian eigenvectors
• Graphs of given order and size and minimum algebraic connectivity
• A lower bound for algebraic connectivity based on the connection-graph-stability method
• Distributed estimation of algebraic connectivity of directed networks
• On the Fiedler value of large planar graphs
• Characterizing trees with large Laplacian energy
• Some graphs determined by their (signless) Laplacian spectra
• Ordering trees with algebraic connectivity and diameter
• Graphs with maximum Laplacian and signless Laplacian Estrada index
• The algebraic connectivity of graphs with given circumference
• The algebraic connectivity of graphs with given matching number
• The seriation problem in the presence of a double Fiedler value
• On distance Laplacian spectral determination of complete multipartite graphs
• Sharp spectral bounds for the edge-connectivity of regular graphs
• Comparison between Laplacian-energy-like invariant and Kirchhoff index
• On some properties of the Laplacian matrix revealed by the RCM algorithm.
• Maximizing the algebraic connectivity for a subclass of caterpillars
• Algebraic connectivity on a subclass of caterpillars
• On the Fiedler value of large planar graphs (extended abstract)
• Spectral properties of unimodular lattice triangulations
• Applications of combinatorial matrix theory to Laplacian matrices of graphs
• On the maximal error of spectral approximation of graph bisection
• Synchrony and complexity in state-related EEG networks: an application of spectral graph theory
• Generating new test instances by evolving in instance space
• On the bounds of Laplacian eigenvalues of \(k\)-connected graphs.
• Further results on permanental bounds for the Laplacian matrix of trees
• The influence of Miroslav Fiedler on spectral graph theory
• On the algebraic connectivity of a double covering graph
• Diameters, distortion, and eigenvalues
• scientific article; zbMATH DE number 2067822 (Why is no real title available?)
• scientific article; zbMATH DE number 2075777 (Why is no real title available?)
• The Group Inverse of the Laplacian Matrix of a Graph
• Graph clustering
• Combinatorial Perron values of trees and bottleneck matrices
• Spectral bounds for the connectivity of regular graphs with given order
• Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra
• scientific article; zbMATH DE number 867649 (Why is no real title available?)
• Graphs with least eigenvalue -2: ten years on
• Computing Vertex Connectivity: New Bounds from Old Techniques
• On Laplacian spectrum of power graphs of finite cyclic and dihedral groups
• Laplacian matrices of general complex weighted directed graphs
• Laplacian spectra of coprime graph of finite cyclic and dihedral groups
• scientific article; zbMATH DE number 7473309 (Why is no real title available?)
• Rigidity of random subgraphs and eigenvalues of stiffness matrices
• Lower bounds for the algebraic connectivity of graphs with specified subgraphs
• On Laplacian spectra of parametric families of closely connected networks with application to cooperative control
• A Note on an Old-Fashioned Algebra for (Disconnected) Graphs
• Hamiltonian graphs of given order and minimum algebraic connectivity
• Gluing of graph Laplacians and their spectra
• Network synchronizability analysis: a graph-theoretic approach
• Algebraic connectivity of k-connected graphs.
• Node-to-node pinning control of complex networks
• Consensus and synchronization problems on small-world networks
• Distributed optimisation and control of graph Laplacian eigenvalues for robust consensus via an adaptive multilayer strategy

Describes a project that uses

Uses Software

• nauty
• AutoGraphiX
• GRAPH

This page was built for publication: Old and new results on algebraic connectivity of graphs

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