Turán-type problems on $[a,b]$-factors of graphs, and beyond

Abstract

Given a set of graphs $\mathcal{H}$, we say that a graph $G$ is \textit{$\mathcal{H}$-free} if it does not contain any member of $\mathcal{H}$ as a subgraph. Let $\text{ex}(n,\mathcal{H})$ (resp. ${\text{ex}}_{sp}(n,\mathcal{H})$) denote the maximum size (resp. spectral radius) of an $n$-vertex $\mathcal{H}$-free graph. Denote by $\text{Ex}(n,\mathcal{H})$ the set of all $n$-vertex $\mathcal{H}$-free graphs with $\text{ex}(n,\mathcal{H})$ edges. Similarly, let ${\mathrm{Ex}}_{sp}(n,\mathcal{H})$ be the set of all $n$-vertex $\mathcal{H}$-free graphs with spectral radius ${\text{ex}}_{sp}(n,\mathcal{H})$. For positive integers $a,b$ with $a⩽b$, an $[a,b]$-factor of a graph $G$ is a spanning subgraph $F$ of $G$ such that $a⩽d_F(v)⩽b$ for all $v\in V(G)$, where $d_F(v)$ denotes the degree of the vertex $v$ in $F.$ Let ${\mathcal{F}}_{a,b}$ be the set of all the $[a,b]$-factors of an $n$-vertex complete graph $K_n$. In this paper, we determine the Turán number $\text{ex}(n,{\mathcal{F}}_{a,b})$ and the spectral Turán number ${\text{ex}}_{sp}(n,{\mathcal{F}}_{a,b}),$ respectively. Furthermore, the bipartite analogue of $\text{ex}(n,{\mathcal{F}}_{a,b})$ (resp. ${\text{ex}}_{sp}(n,{\mathcal{F}}_{a,b})$) is also obtained. All the corresponding extremal graphs are identified. Consequently, one sees that ${\mathrm{Ex}}_{sp}(n,{\mathcal{F}}_{a,b})\subseteq \text{Ex}(n,{\mathcal{F}}_{a,b})$ holds for graphs and bipartite graphs. This partially answers an open problem proposed by Liu and Ning \cite{LN2023}. Our results may deduce a main result of Fan and Lin \cite{FL2022}.

22 pages; 1 figure