Three conjectures in extremal spectral graph theory
Three conjectures in extremal spectral graph theory
复制标题
DOI：
10.1016/j.jctb.2017.04.006
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Michael Tait;Josh Tobin
中科院分区：
文献类型：
--
作者：
Michael Tait;Josh Tobin
我们证明了关于某些图族上的谱不变量最大化的三个猜想。我们最困难的结果是P2和Pn−2的并是所有平面图上具有最大谱半径的唯一图。这是1991年由Boots和Royle猜测的，1993年由曹和文斯独立猜测的。类似地，我们证明了1990年Cvetković和Rowlinson的一个猜想，即最大谱半径的唯一外平面图是一个顶点和Pn−1的联结。指出菠萝图是使谱半径减去平均度最大化的唯一连通图。为了证明我们的定理，我们使用一个所谓的极值图的主导特征向量来推导该图的结构性质。
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 P n− 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 P n− 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.