UC San Diego

We address several problems in spectral graph theory, with a common theme of optimizing or computing a spectral graph invariant, such as the spectral radius or spectral gap, over some family of graphs. In particular, we study measures of graph irregularity, we bound the adjacency spectral radius over all outerplanar and planar graphs, and finally we determine the spectral gap of reversal graphs and a family of graphs that generalize the prefix reversal graph.

Firstly we study two measures of graph irregularity, the principal ratio and the difference between the spectral radius of the adjacency matrix and the average degree. For the principal ratio, we show that the graphs which maximize this statistic are the kite graphs, which are a clique with a pendant path, when the number of vertices is sufficiently large. This answers a conjecture of Cioabă and Gregory. For the second graph irregularity measure, we show that the connected graphs which maximize it are pineapple graphs, answering a conjecture of Aouchiche et al.

Secondly we investigate the maximum spectral radius of the adjacency matrix over all graphs on n vertices within certain well-known graph families. Our main result is showing that the planar graph on n vertices with maximal adjacency spectral radius is the join P 2 + P n−2 , when n is sufficiently large. This was conjectured by Boots and Royle. Additionally, we identify the outerplanar graph with maximal spectral radius, answering a conjecture of Cvetkovic̀ and Rowlinson.

Finally, we determine the spectral gap of various Cayley graphs of the symmetric group Sn , which arise in the context of substring reversals. This includes an elementary proof that the prefix reversal (or pancake flipping graph) has spectral gap one, originally

proved via representation theory by Cesi. We generalize this by showing that a large family of related graphs all have unit spectral gap.