2022/08/12 by Yair Caro, Balázs Patkós, Caro, Yair +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · doi:10.48550/arxiv.2208.06126
openalex publication_date 2022/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
As a variant of the much studied Turán number, ex(n,F), the largest number of edges that an n-vertex F-free graph may contain, we introduce the connected Turán number exc(n,F), the largest number of edges that an n-vertex connected F-free graph may contain. We focus on the case where the forbidden graph is a tree. The celebrated conjecture of Erdős and Sós states that for any tree T, we have ex(n,T)≤(|T|-2)(n)/(2). We address the problem how much smaller exc(n,T) can be, what is the smallest possible ratio of exc(n,T) and (|T|-2)(n)/(2) as |T| grows. We also determine the exact value of exc(n,T) for small trees, in particular for all trees with at most six vertices. We introduce general constructions of connected T-free graphs based on graph parameters as longest path, matching number, branching number, etc.