Three conjectures in extremal spectral graph theory

DOI10.1016/J.JCTB.2017.04.006zbMath1368.05098arXiv1606.01916OpenAlexW2963128445MaRDI QIDQ2399353

Publication date: 22 August 2017

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: 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 KH{o}vari-S'os-Tur'an Theorem applied to $mathrm{ex}left(n, K_{2,t} ight)$, and a partial solution to an old problem of ErdH{o}s on making a triangle-free graph bipartite.

Full work available at URL: https://arxiv.org/abs/1606.01916

zbMATH Keywords

spectral radius planar graph extremal graph theory graph irregularity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Cites Work

Related Items (56)

On the spread of outerplanar graphs ⋮ Graphs determined by their $A_\alpha$-spectra ⋮ Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals ⋮ On the spectral radius, energy and Estrada index of the arithmetic–geometric matrix of a graph ⋮ Sharp upper bounds on the $Q$-index of (minimally) 2-connected graphs with given size ⋮ On the spectral radius, energy and Estrada index of the Sombor matrix of graphs ⋮ The spectral radius of graphs with no $k_{2,t}$ minor ⋮ On the spectral radius of graphs without a star forest ⋮ A unique characterization of spectral extrema for friendship graphs ⋮ Spectral extrema of $K_{s,t}$-minor free graphs -- on a conjecture of M. Tait ⋮ The signless Laplacian spectral radius of graphs with forbidding linear forests ⋮ A sharp upper bound on the spectral radius of $C_5$-free/$C_6$-free graphs with given size ⋮ Spectral properties of the eccentricity matrix of graphs ⋮ On the eigenvalues of $A_\alpha $-matrix of graphs ⋮ On the spectral radius of minimally 2-(edge)-connected graphs with given size ⋮ A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs ⋮ On the $A_\alpha $-spectral radius of graphs with given size ⋮ Outerplanar Turán numbers of cycles and paths ⋮ Spectral extremal graphs for the bowtie ⋮ A complete solution to the Cvetković–Rowlinson conjecture ⋮ Refinement on Spectral Turán’s Theorem ⋮ Maximum spectral radius of outerplanar 3‐uniform hypergraphs ⋮ On minimally 2-(edge)-connected graphs with extremal spectral radius ⋮ Unimodality of principal eigenvector and its applications ⋮ The maximum spectral radius of graphs without spanning linear forests ⋮ The unique spectral extremal graph for intersecting cliques or intersecting odd cycles ⋮ Connected graphs of fixed order and size with maximal $A_\alpha $-index: the one-dominating-vertex case ⋮ A spectral extremal problem on non-bipartite triangle-free graphs ⋮ The spectral radius of minor-free graphs ⋮ Characterization of outerplanar graphs whose second largest eigenvalue is at most 1 ⋮ The maximum spectral radius of graphs of given size with forbidden subgraph ⋮ High dimensional Hoffman bound and applications in extremal combinatorics ⋮ Unnamed Item ⋮ Spectral extremal results with forbidding linear forests ⋮ Extremal spectral radius of $K_{3,3}/K_{2,4}$-minor free graphs ⋮ The spectral even cycle problem ⋮ On the maximum spread of planar and outerplanar graphs ⋮ Spectral extremal graphs without intersecting triangles as a minor ⋮ On the irregularity of uniform hypergraphs ⋮ The Colin de Verdière parameter, excluded minors, and the spectral radius ⋮ On the spectral radius and energy of the weighted adjacency matrix of a graph ⋮ The extremal $\alpha $-index of outerplanar and planar graphs ⋮ Unnamed Item ⋮ The extremal $\alpha $-index of graphs with no 4-cycle and 5-cycle ⋮ Spectral extremal results on trees ⋮ Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs ⋮ Spectral extrema of 1-planar graphs ⋮ A spectral Erdős-Rademacher theorem ⋮ Spectral radius and rainbow Hamilton paths of a graph ⋮ The high order spectral extremal results for graphs and their applications ⋮ Spectral extremal problem on $t$ copies of $\ell$-cycles ⋮ Eigenvalues and triangles in graphs ⋮ The graphs cospectral with the pineapple graph ⋮ Ordering graphs with given size by their signless Laplacian spectral radii ⋮ Positive semidefiniteness of $A_\alpha (G)$ on some families of graphs ⋮ The maximum spectral radius of non-bipartite graphs forbidding short odd cycles

This page was built for publication: Three conjectures in extremal spectral graph theory