期刊
JOURNAL OF COMBINATORIAL THEORY SERIES B
卷 126, 期 -, 页码 137-161出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2017.04.006
关键词
Spectral radius; Planar graph; Graph irregularity; Extremal graph theory
类别
资金
- NSF [DMS-1606350, DMS-1362650]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据