Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777611 | Journal of Combinatorial Theory, Series B | 2017 | 25 Pages |
Abstract
We prove three conjectures regarding the maximization of spectral invariants over certain families of graphs. Our most difficult result is that the join of P2 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 CvetkoviÄ 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael Tait, Josh Tobin,