Subdivision-free graphs with the maximum spectral radius

Abstract

Given a graph family $\mathbb{H}$, let $\mathrm{SPEX}(n,{\mathbb{H}}_{\mathrm{sub}})$ denote the set of $n$-vertex $\mathbb{H}$-subdivision-free graphs with the maximum spectral radius. In this paper, we investigate the problem of graph subdivision from a spectral extremal perspective, with a focus on the structural characterization of graphs in $\mathrm{SPEX}(n,{\mathbb{H}}_{\mathrm{sub}})$. For any graph $H\in \mathbb{H}$, let $\hat{I}\pm (H)$ denote its independence number. Define ${\hat{I}}_{\mathbb{H}}^3:={\min }_{H\in \mathbb{H}}\{|H|-\hat{I}\pm (H)-1\}$. We prove that every graph in $\mathrm{SPEX}(n,{\mathbb{H}}_{\mathrm{sub}})$ contains a spanning subgraph isomorphic to $K_{{\hat{I}}_{\mathbb{H}}^3}\vee (n-{\hat{I}}_{\mathbb{H}}^3)K_1$, which is obtained by joining a ${\hat{I}}_{\mathbb{H}}^3$-clique with an independent set of $n-{\hat{I}}_{\mathbb{H}}^3$ vertices. This extends a recent result by Zhai, Fang, and Lin concerning spectral extremal problems for $\mathbb{H}$-minor-free graphs.

17 pages, 1 figure