solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看216次
Three conjectures in extremal spectral graph theory. (arXiv:1606.01916v2 [math.CO] UPDATED)
来源于:arXiv
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\'c 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. Using this
setup, we give short proofs of several old results: Mantel's Theorem, Stanley's
edge bound and extensions, the K\H{o}vari-S\'os-Tur\'an Theorem applied to
$\m 查看全文>>