2024/03/11 by Xiying Yuan, Zhou, Junpeng, Yuan, Xiying
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2403.06637
openalex publication_date 2024/03/11 · openalex created_date 2024/03/13 · openalex updated_date 2026/08/01
An r-uniform hypergraph (r-graph for short) is linear if any two edges intersect at most one vertex. Let F be a given family of r-graphs. An r-graph H is called F-free if H does not contain any member of F as a subgraph. The Turán number of F is the maximum number of edges in any F-free r-graph on n vertices, and the linear Turán number of F is defined as the Turán number of F in linear host hypergraphs. An r-uniform linear path Pr_ℓ of length ℓ is an r-graph with edges e1,…,e_ℓ such that |V(ei)∩ V(ej)|=1 if |i-j|=1, and V(ei)∩ V(ej)=∅ for i≠ j otherwise. Gyárfás et al. [European J. Combin. (2022) 103435] obtained an upper bound for the linear Turán number of P_ℓ3. In this paper, an upper bound for the linear Turán number of P_ℓr is obtained, which generalizes the known result of P_ℓ3 to any P_ℓr. Furthermore, some results for the linear Turán number and Turán number of several linear star-path forests are obtained.