On graphs with equal algebraic and vertex connectivity
By S. Kirkland, Jason J. Molitierno, M. Neumann, Bryan L. Shader. 2002
83 citations recorded by the source corpus.
Let G be an undirected unweighted graph on n vertices, let L be its Laplacian matrix, and let L#=(l#i,j) be the group inverse of L. It is known that for Z(L#):=(1/2)max1⩽i,j⩽n∑s=1n|li,s#−lj,s#|, the quantity 1/Z(L#) is a lower bound on the algebraic connectivity a(G) of G, while the vertex connectivity of G, v(G), is an upper bound on a(G). We characterize the graphs G for which v(G)=a(G) and subsequently prove that if n⩾v(G)2, then v(G)=a(G) holds if and only if 1/Z(L#)=a(G)=v(G). We close with an example showing that the equality 1/Z(L#)=a(G) does not necessarily imply that 1/Z(L#)=a(G)=v(G).
Subfields: Computer Networks and Communications, Geometry and Topology, Materials Chemistry
View Paper: https://www.semanticscholar.org/paper/3b73e50d6ea101966f73a9dbb1916afc765dec14
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
In Geometry and Topology
In Materials Chemistry
Citations in the corpus
- The Laplacian eigenvalues of graphs: a survey (2011, background): “[53] obtained the necessary and sufficient conditions for the second smallest eigenvalue equal to the vertex connectivity.”
- Old and new results on algebraic connectivity of graphs (2007, methodology): “Hence, this could not be different with respect to the algebraic connectivity, as described in [4,22,47,49].”
- Linear Algebra and its Applications (2010, methodology): “We note that the transformed system is introduced for analysis purposes only and that our numerical methods will be applied to system (1.2).”