Two adventures in spectral graph theory

In his landmark paper, How to Draw a Graph, Tutte explores the spring energy model of straight line graph drawings. Using semidefinite programming, Goemans and Williamson further explore the utility of energy in graph embeddings in their investigation of maxcut of a graph. For our first problem we take ideas from both Tutte and Goemans and Williamson. We use semidefinite programming to find minimal energy graph representations, and investigate a natural parameter we define which arises from this, ρ. For G a random regular graph, or regular graph of high girth, we show that ρ is bounded by the second largest eigenvalue of the adjacency matrix of G. For our second problem, we again find inspiration from Tutte. A fundamental family of totally unimodular matrices introduced by Tutte are network matrices. A network matrix is defined based on a graph G and a tree T on a common vertex set. The positive semidefinite matrix NNT obeys the Matrix Tree Theorem and generalizes the Laplacian of G. We investigate the spectrum of this matrix, in particular the highest eigenvalue λmax. When G = Kn we find the trees maximizing and minimizing λmax. When T is restricted to be a subgraph of G we give a rough structure theorem determining when λmax is bounded. Additionally we find a natural edge connectivity property that implies λmax is minimized by taking T to be a star. Lastly we find an alternate proof of correctness of the famous Gomory-Hu tree theorem.