Leírás
Abstract:
In the first part of the talk, we will investigate the maximum number $ex_c(n,T)$ of edges that an $n$-vertex connected $T$-free graph can have, where $T$ is a tree. We determine this value for many small trees. We give general construction based on several parameters of trees. We also address the problem of finding the smallest ratio the connected Turán number and the ordinary Turán number can have.
In the second part of the talk, motivated by a theorem of Győri and Lovász, we consider the following problem. For a connected graph $G$ on $n$ vertices and $m$ edges determine the number $P(G,k)$ of unordered solutions of positive integers $\sum_{i=1}^k m_i = m$ such that every $m_i$ is realized by a connected subgraph $H_i$ of $G$ with $m_i$ edges.
We prove various lower bounds on $P(G,k)$ as a function of the number $n$ of vertices in $G$, as a function of the average degree $d$ of $G$, and also as the size $CMC_r(G)$ of $r$-partite connected maximum cuts of $G$. Those three lower bounds are tight up to a multiplicative constant.
Joint work with Yair Caro, Zsolt Tuza, and Máté Vizer.