Connected Turán number of trees

Caro, Yair and Patkós, Balázs and Tuza, Zsolt (2024) Connected Turán number of trees. ARS MATHEMATICA CONTEMPORANEA. ISSN 1855-3966

Preview

Text 2208.06126v1.pdf Available under License Creative Commons Attribution. Download (237kB) | Preview

Abstract

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´an 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.

Actions (login required)

Edit Item