# zbMATH — the first resource for mathematics

Three conjectures in extremal spectral graph theory. (English) Zbl 1368.05098
Summary: 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 B. N. Boots and G. F. Royle [“A conjecture on the maximum value of the principal eigenvalue of a planar graph”, Geogr. Anal. 23, No. 3, 276–282 (1991; doi:10.1111/j.1538-4632.1991.tb00239.x)], and independently by D. Cao and A. Vince [Linear Algebra Appl. 187, 251–257 (1993; Zbl 0786.05056)]. Similarly, we prove a conjecture of D. Cvetković and P. Rowlinson [Linear Multilinear Algebra 28, No. 1–2, 3–33 (1990; Zbl 0744.05031)] 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 M. Aouchiche et al. [Eur. J. Oper. Res. 191, No. 3, 661–676 (2008; Zbl 1160.90494)] 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.

##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C35 Extremal problems in graph theory 05C10 Planar graphs; geometric and topological aspects of graph theory
##### Citations:
Zbl 0786.05056; Zbl 0744.05031; Zbl 1160.90494
Full Text: