Graphs without theta subgraphs
Graphs without theta subgraphs
复制标题
DOI：
10.1016/j.jctb.2018.05.003
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Jacques Verstraëte;Jason S. Williford
中科院分区：
文献类型：
--
作者：
Jacques Verstraëte;Jason S. Williford
设θ 3，4表示由具有相同端点对的四条边的三条内部不相交路组成的图。本文给出了任意n-顶点θ 3，4-free图的最大边数的一个n5/4阶下界，它与Faudree和Simonovits的一个上界在一个绝对常数因子下相匹配.这种结构本质上是代数的，源于有限域上的方程，也许是证明八边形的图兰数也是n 5/4阶的证据。
Let θ 3, 4 denote the graph consisting of three internally disjoint paths of four edges with the same pair of endpoints. In this paper, we give a lower bound of order n 5/4 on the greatest number of edges of any n-vertex θ 3, 4-free graph, matching an earlier upper bound by Faudree and Simonovits up to an absolute constant factor. The construction is algebraic in nature, arising from equations over finite fields, and is perhaps some evidence that the Turán Number for the octagon is also of order n 5/4.