论文标题
连接的Turán树木数量
Connected Turán number of trees
论文作者
论文摘要
作为研究众多的Turán号码的变体，$ ex（n，f）$，可能包含$ n $ n $ vertex $ f $ - f $ f $ f $ f $ f $ f $ f $ f $ f $ f $ f $ f $ ex_c（n，f）$的最大边缘，最多的边缘，是$ n $ n $ n $ n $ - vertex connected $ f $ f $ f $ f $ f的图形。我们专注于禁止图是树的情况。著名的Erdős和Sós的猜想指出，对于任何树$ t $，我们都有$ ex（n，t）\ le（| t | -2）\ frac {n} {2} $。我们解决了问题，$ ex_c（n，t）$可以是多少，$ ex_c（n，t）$和$（| t | -2）\ frac {n} {2} $的最小可能比率是$ | t | $ grow。我们还确定了小树的$ ex_c（n，t）$的确切值，特别是所有最多六个顶点的树。我们介绍了基于图形参数的连接$ t $ free图的一般构造，最长的路径，匹配号码，分支号码等。
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 $ex_c(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)\le(|T|-2)\frac{n}{2}$. We address the problem how much smaller $ex_c(n,T)$ can be, what is the smallest possible ratio of $ex_c(n,T)$ and $(|T|-2)\frac{n}{2}$ as $|T|$ grows. We also determine the exact value of $ex_c(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.
