The Colin de Verdi `ere parameter, excluded minors, and the spectral\n radius

2017/03/28 by Michael Tait, Tait, Michael · 2 citations
Mathematics · Computer Science · #Graph theory and applications #Matrix Theory and Algorithms #Spectral Theory in Mathematical Physics

paper · pdf · doi:10.48550/arxiv.1703.09732

Abstract

In this paper we characterize graphs which maximize the spectral radius of\ntheir adjacency matrix over all graphs of Colin de Verdi `ere parameter at most\nm. We also characterize graphs of maximum spectral radius with no H as a\nminor when H is either K_r or K_s,t. Interestingly, the extremal graphs\nmatch those which maximize the number of edges over all graphs with no H as a\nminor when r and s are small, but not when they are larger.\n

Cited by

• Spectral Turán problems for suspensions of balanced trees
• Spectral extrema of graphs forbidding a fan

Related

• On the maximum spectral radius of connected graphs with a prescribed order and size
• Two spectral extremal results for graphs with given order and rank
• A generalization on spectral extrema of K_s,t-minor free graphs
• Extremal spectral radius of degree-based weighted adjacency matrices of graphs with given order and size
• Extremal graphs for the maximum A_α-spectral radius of graphs with order and size