Old and new results on algebraic connectivity of graphs

DOI10.1016/j.laa.2006.08.017zbMath1115.05056OpenAlexW2042018868WikidataQ125749201 ScholiaQ125749201MaRDI QIDQ876302

Nair Maria Maia De 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

extremal graphslimit pointsFiedler vectorsbounds for the algebraic connectivityLaplacian integral graphsLaplacian of graphvertex and edge connectivities

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

Consensus dynamics on random rectangular graphs ⋮ Quantum algorithm for Boolean equation solving and quantum algebraic attack on cryptosystems ⋮ Sixty years of network reliability ⋮ A lower bound for the algebraic connectivity of a graph in terms of the domination number ⋮ Spectral Bounds for the Connectivity of Regular Graphs with Given Order ⋮ Signless Laplacian spectral characterization of some disjoint union of graphs ⋮ A new method optimizing the subgraph centrality of large networks ⋮ Laplacian spectrum of comaximal graph of the ring \(\mathbb{Z}_n\) ⋮ Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices ⋮ Spectral properties of unimodular lattice triangulations ⋮ Graphs with maximum Laplacian and signless Laplacian Estrada index ⋮ A new approach based on spectral graph theory to avoiding enclosed holes in topology optimization ⋮ Augmenting the algebraic connectivity for certain families of graphs ⋮ The algebraic connectivity of graphs with given circumference ⋮ On (distance) signless Laplacian spectra of graphs ⋮ New conjectures on algebraic connectivity and the Laplacian spread of graphs ⋮ On the maximal error of spectral approximation of graph bisection ⋮ The algebraic connectivity of graphs with given matching number ⋮ Lower bounds for the algebraic connectivity of graphs with specified subgraphs ⋮ On the bounds of Laplacian eigenvalues of k-connected graphs ⋮ The Group Inverse of the Laplacian Matrix of a Graph ⋮ Generating new test instances by evolving in instance space ⋮ Maxima of the Laplacian spectral radius of (minimally) 2-connected graphs with fixed size ⋮ Sign-changing diagonal perturbations of Laplacian matrices of graphs ⋮ Graphs with given diameter maximizing the algebraic connectivity ⋮ Algebraic connectivity of network-of-networks having a graph product structure ⋮ Spectral and structural properties of random interdependent networks ⋮ The influence of Miroslav Fiedler on spectral graph theory ⋮ Schur reduction of trees and extremal entries of the Fiedler vector ⋮ Tighter spectral bounds for the cut size, based on Laplacian eigenvectors ⋮ The seriation problem in the presence of a double Fiedler value ⋮ Algebraic connectivity and disjoint vertex subsets of graphs ⋮ Graphs of given order and size and minimum algebraic connectivity ⋮ A lower bound for algebraic connectivity based on the connection-graph-stability method ⋮ Combinatorial Perron values of trees and bottleneck matrices ⋮ Absolute algebraic connectivity of double brooms and trees ⋮ Distributed estimation of algebraic connectivity of directed networks ⋮ On the Fiedler value of large planar graphs ⋮ Characterizing trees with large Laplacian energy ⋮ On distance Laplacian spectral determination of complete multipartite graphs ⋮ Diameters, distortion, and eigenvalues ⋮ Sharp spectral bounds for the edge-connectivity of regular graphs ⋮ On synchronization in heterogeneous FitzHugh-Nagumo networks ⋮ An interlacing technique for spectra of random walks and its application to finite percolation clusters ⋮ Graph clustering ⋮ Some graphs determined by their (signless) Laplacian spectra ⋮ On ordering bicyclic graphs with respect to the Laplacian spectral radius ⋮ Unnamed Item ⋮ Optimal grid drawings of complete multipartite graphs and an integer variant of the algebraic connectivity ⋮ Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra ⋮ Ordering trees with algebraic connectivity and diameter ⋮ New bounds for the signless Laplacian spread ⋮ Graphs with least eigenvalue \(-2\): ten years on ⋮ Synchronization in large-scale nonlinear network systems with uncertain links ⋮ \texttt{PQser:} a Matlab package for spectral seriation ⋮ Laplacian matrices of general complex weighted directed graphs ⋮ On Laplacian spectra of parametric families of closely connected networks with application to cooperative control ⋮ On trees with algebraic connectivity greater than or equal to \(2(1-\cos(\frac{\pi}{7}))\) ⋮ Hubs-biased resistance distances on graphs and networks ⋮ Computing tight upper bounds on the algebraic connectivity of certain graphs ⋮ Ordering trees and graphs with few cycles by algebraic connectivity ⋮ Algebraic connectivity and degree sequences of trees ⋮ A survey of automated conjectures in spectral graph theory ⋮ A tight upper bound on the spectral radius of bottleneck matrices for graphs ⋮ Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality ⋮ A sharp upper bound on algebraic connectivity using domination number ⋮ Maximizing algebraic connectivity for certain families of graphs ⋮ Unnamed Item ⋮ On algebraic connectivity augmentation ⋮ A divide-and-conquer bound for aggregate's quality and algebraic connectivity ⋮ Further results on permanental bounds for the Laplacian matrix of trees ⋮ Some results on the Laplacian spectrum ⋮ 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 ⋮ The algebraic connectivity of graphs under perturbation ⋮ Comparison between Laplacian--energy--like invariant and Kirchhoff index ⋮ Improving connectivity of compromised digital networks via algebraic connectivity maximisation ⋮ A conjecture on the algebraic connectivity of connected graphs with fixed girth ⋮ On algebraic connectivity of directed scale-free networks ⋮ Algebraic connectivity and doubly stochastic tree matrices ⋮ Hamiltonian graphs of given order and minimum algebraic connectivity ⋮ Decentralized local-global connectivity maintenance for networked robotic teams ⋮ Gluing of graph Laplacians and their spectra ⋮ 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 ⋮ Synchrony and complexity in state-related EEG networks: an application of spectral graph theory ⋮ The Laplacian spectral radius of tricyclic graphs with \(n\) vertices and \(k\) pendant vertices ⋮ `Hubs-repelling' Laplacian and related diffusion on graphs/networks ⋮ On Laplacian spectrum of power graphs of finite cyclic and dihedral groups ⋮ 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 ⋮ Ordering trees by the Laplacian coefficients ⋮ Spectra of graphs resulting from various graph operations and products: a survey ⋮ On the algebraic connectivity of some caterpillars: a sharp upper bound and a total ordering ⋮ Eigenvalues and edge-connectivity of regular graphs ⋮ Network synchronizability analysis: A graph-theoretic approach ⋮ Algebraic connectivity of k-connected graphs ⋮ Laplacian spectra of Coprime Graph of finite cyclic and Dihedral groups ⋮ Addressing the envelope reduction of sparse matrices using a genetic programming system

Uses Software

• nauty
• AutoGraphiX
• GRAPH

Cites Work

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

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