The Tur\'an number of path-star forests

arXiv2305.11680MaRDI QIDQ6437215FDOQ6437215

Xiaona Fang, Yaojun Chen, Lihua You

Publication date: 19 May 2023

Abstract: The Tur'an number of a graph $F$, denoted $ex(n,F)$, is the maximum number of edges in an $F$-free graph on $n$ vertices. Let $P_{ell}$, $S_{ell}$ denote the path and star on $ell$ vertices, respectively. A linear forest is a forest whose connected components are paths. In 2013, Lidick'y et al. considered the Tur'an number of linear forest and $$ for sufficiently large $n$. Recently, Fang and Yuan determine the Tur'an numbers of $$, $$, $$ for $n$ appropriately large and characterized the corresponding extremal graphs. In this paper, We determine $$ for all $ngeq16$ and characterize all extremal graphs, which partially confirms a conjecture proposed by Yuan and Zhang [L.T. Yuan, X.D. Zhang, J. Graph. Theory 98(3) (2021) 499--524]. And we determine the Tur'an numbers of $$ for $n$ appropriately large, where $a_{j}leq2k_2+2sumlimit{s}_{i=1}^{k_1}lfloorfracel{l}_{i}2floor-2j$ for any $jin[k_2]$, which generalizes the results of Fang and Yuan. The corresponding extremal graphs are also completely characterized

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

This page was built for publication: The Tur\'an number of path-star forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437215)