The formula for Turan number of spanning linear forests
The formula for Turan number of spanning linear forests
复制标题
跨越线性森林的图兰数公式
DOI：
10.1016/j.disc.2020.111924
复制
发表时间：
2020
影响因子：
0.8
通讯作者：
Wang Jian
中科院分区：
文献类型：
--
作者：
Ning Bo;Wang Jian
设F是一个图族。Turán数ex（n; F）定义为n阶图中无F的最大边数。在1959年，Erdans和Gallai确定了M k+ 1的图兰数如下：ex（n; M k+ 1）= max 2 k+ 1 2，n 2− n− k 2。从那时起，有很多关于线性森林的图兰数的研究。线性森林是一个图，它的连通分支都是路径或孤立点。设Ln，k是所有n阶线性森林的族.本文证明了ex（n; Ln，k）= maxk 2，n2 − n-k − 122 + c，其中当k为奇数时c= 0，否则c= 1.这确定了具有给定Hamilton完成数的非Hamilton图中的最大边数，并且作为特例解决了Wang和Yang（2019）中的两个公开问题。此外，我们还证明了我们的主要定理蕴涵着Erdens-Gallai定理，并利用闭包和计数技巧给出了它的一个简短的新证明。最后，我们推广我们的定理，它蕴涵着著名的Erd匹配猜想。
Let F be a family of graphs. The Turán number e x (n; F) is defined to be the maximum number of edges in a graph of order n that is F-free. In 1959, Erdős and Gallai determined the Turán number of M k+ 1 (a matching of size k+ 1) as follows: e x (n; M k+ 1)= max 2 k+ 1 2, n 2− n− k 2. Since then, there has been a lot of research on Turán number of linear forests. A linear forest is a graph whose connected components are all paths or isolated vertices. Let L n, k be the family of all linear forests of order n with k edges. In this paper, we prove that e x (n; L n, k)= max k 2, n 2− n− k− 1 2 2+ c, where c= 0 if k is odd and c= 1 otherwise. This determines the maximum number of edges in a non-Hamiltonian graph with given Hamiltonian completion number and also solves two open problems in Wang and Yang (2019) as special cases. Moreover, we show that our main theorem implies Erdős–Gallai Theorem and also gives a short new proof for it by the closure and counting techniques. Finally, we generalize our theorem to a conjecture which implies the famous Erdős Matching Conjecture.