Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B
Volume 126, Issue -, Pages 137-161Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2017.04.006
Keywords
Spectral radius; Planar graph; Graph irregularity; Extremal graph theory
Categories
Funding
- NSF [DMS-1606350, DMS-1362650]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available