Spectral extrema of Ks,t-minor free graphs - On a conjecture of M. Tait

Minors play a key role in graph theory, and extremal problems on forbidding minors have attracted appreciable amount of interest in the past decades. In this paper, we focus on spectral extrema of K-s,K-t-minor free graphs, and determine extremal graphs with maximum spectral radius over all K-s,K-t-minor free graphs of sufficiently large order. This generalizes and improves several previous results. For t >= s >= 2, our result completely solves Tait's conjecture. For t >= s = 1, our result gives a spectral analogue of a theorem due to Ding, Johnson and Seymour, which determines the maximum number of edges in K-1,K-t-minor free connected graphs. Some spectral and structural tools, such as, local edge maximality, local degree sequence majorization and double eigenvectors transformation, are used to characterize structural properties of extremal graphs. (C) 2022 Elsevier Inc. All rights reserved.

Automated summary

This paper focuses on the spectral extrema of K-s,K-t-minor free graphs and determines the extremal graphs with maximum spectral radius among all K-s,K-t-minor free graphs of sufficiently large order. The results generalize and improve previous findings, solving conjectures and providing spectral analogues of theorems. Spectral and structural tools are used to characterize the properties of extremal graphs.