Algebraic Connectivity

Graph Theory · Axiom Academy

Understanding graph connectivity through the Fiedler value and spectral graph theory The algebraic connectivity or Fiedler value of a graph G, denoted λ₂(G), is the second smallest eigenvalue of the graph's Laplacian matrix. The Laplacian matrix L = D - A, where D is the degree matrix and A is the adjacency matrix. 2. Connection to Graph Connectivity The Fiedler value completely characterizes whether a graph is connected: λ₁ = 0 always (with eigenvector of all ones) If G is disconnected, λ₂ = 0 (multiplicity equals number of components) 3. Larger λ₂ Means "More Connected" Among connected graphs, a larger Fiedler value indicates stronger connectivity. The value λ₂ measures how difficult it is to partition the graph into disconnected components. Path graph Pₙ: λ₂ ≈ O(1/n²) - weakly connected Cycle graph Cₙ: λ₂ ≈ O(1/n²) - weakly connected Complete graph Kₙ: λ₂ = n - strongly connected Expander graphs: λ₂ bounded away from 0 regardless of size 4. The Fiedler Vector and Graph Partitioning The Fiedler vector is the eigenvector corresponding to λ₂. It provides valuable information for partitioning the graph into two communities. Assign vertices with positive entries to one set Assign vertices with negative entries to another set This minimizes the cut between sets (approximately) 5. Bounds Relating λ₂ to Edge Connectivity The Fiedler value is closely related to the edge connectivity κ(G), which is the minimum number of edges whose removal disconnects the graph.

This is the written version of the interactive lesson above. See the full Graph Theory course.