The Turan number for spanning linear forests
The Turan number for spanning linear forests
复制标题
跨越线性森林的图兰数
DOI：
10.1016/j.dam.2018.07.014
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Yang Weihua
中科院分区：
文献类型：
--
作者：
Wang Jian;Yang Weihua
对于一个图集F，极值数ex（n; F）是不包含与F中某个图同构的任何子图的n阶图的最大边数。如果F包含n个顶点的图，那么我们通常称这个问题为生成图兰问题。一个线性森林是一个图，它的连通分支都是路径和孤立点。在本文中，我们设Lnk是所有至少有n-k + 1条边的n阶线性森林的集合。证明了当n≥ 3 k，k≥ 2时，ex（n; Lnk）= n-k +12 + O（k2）.显然，当k= o（n）时，结果很有趣。
For a set of graphs F, the extremal number e x (n; F) is the maximum number of edges in a graph of order n not containing any subgraph isomorphic to some graph in F. If F contains a graph on n vertices, then we often call the problem a spanning Turán problem. A linear forest is a graph whose connected components are all paths and isolated vertices. In this paper, we let L n k be the set of all linear forests of order n with at least n− k+ 1 edges. We prove that when n≥ 3 k and k≥ 2, e x (n; L n k)= n− k+ 1 2+ O (k 2). Clearly, the result is interesting when k= o (n).