Three conjectures in extremal spectral graph theory

摘要

We prove three conjectures regarding the maximization of spectral invariants over certain families of graphs. Our most difficult result is that the join of P-2 and Pn-2 is the unique graph of maximum spectral radius over all planar graphs. This was conjectured by Boots and Royle in 1991 and independently by Cao and Vince in 1993. Similarly, we prove a conjecture of Cvetkovie and Rowlinson from 1990 stating that the unique outerplanar graph of maximum spectral radius is the join of a vertex and Pn-1. Finally, we prove a conjecture of Aouchiche et al. from 2008 stating that a pineapple graph is the unique connected graph maximizing the spectral radius minus the average degree. To prove our theorems, we use the leading eigenvector of a purported extremal graph to deduce structural properties about that graph. (C) 2017 Elsevier Inc. All rights reserved.