Turán-type problems on \([a, b]\)-factors of graphs, and beyond
The electronic journal of combinatorics, Tome 31 (2024) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a set of graphs $\mathcal{H}$, we say that a graph $G$ is $\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\leqslant b$, an $[a,b]$-factor of a graph $G$ is a spanning subgraph $F$ of $G$ such that $a\leqslant d_F(v)\leqslant 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\'an number $\text{ex}(n,\mathcal{F}_{a,b})$ and the spectral Tur\'an 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 (arXiv:2307.14629, 2023). Our results may deduce a main result of Fan and Lin (arXiv:2211.09304v1, 2021).
DOI : 10.37236/12106
Classification : 05C35, 05C70, 05C50, 05C30
Mots-clés : extremal graphs, spectral Turán number

Yifang Hao    ; Shuchao Li  1

1 Central China Normal University
@article{10_37236_12106,
     author = {Yifang Hao and Shuchao Li},
     title = {Tur\'an-type problems on \([a, b]\)-factors of graphs, and beyond},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {3},
     doi = {10.37236/12106},
     zbl = {1548.05183},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12106/}
}
TY  - JOUR
AU  - Yifang Hao
AU  - Shuchao Li
TI  - Turán-type problems on \([a, b]\)-factors of graphs, and beyond
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12106/
DO  - 10.37236/12106
ID  - 10_37236_12106
ER  - 
%0 Journal Article
%A Yifang Hao
%A Shuchao Li
%T Turán-type problems on \([a, b]\)-factors of graphs, and beyond
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/12106/
%R 10.37236/12106
%F 10_37236_12106
Yifang Hao; Shuchao Li. Turán-type problems on \([a, b]\)-factors of graphs, and beyond. The electronic journal of combinatorics, Tome 31 (2024) no. 3. doi: 10.37236/12106

Cité par Sources :