What Eigenvectors and Eigenvalues Reveal About Graphs: Distance and Resistance Laplacians

What can the signs of an eigenvector tell us about a graph? Can eigenvalues identify a particular class of graphs? I will explore these questions by comparing the ordinary graph Laplacian with two related matrices built from shortest-path distances and effective resistances.

Fiedler’s theorem says that the vertices corresponding to the nonnegative entries of an eigenvector for algebraic connectivity induce a connected subgraph, as do those corresponding to its nonpositive entries. This offers a useful perspective on dividing a network using eigenvectors. I will discuss a corresponding theorem for the resistance Laplacian, where the relevant eigenvector belongs to the largest eigenvalue. On unweighted trees, effective resistance equals path distance, so the result also applies to the distance Laplacian.

I will then turn to eigenvalues. A classical theorem characterises threshold graphs through a relationship between Laplacian eigenvalues and vertex degrees. An analogous characterisation holds for the distance Laplacian. For the resistance Laplacian, the corresponding formula fails for some threshold graphs but holds precisely for complete split graphs within the connected threshold class.  

The talk will use examples throughout and assume no prior knowledge of spectral graph theory.

Register Now