Turán Numbers of Subdivided Graphs
Turán Numbers of Subdivided Graphs
复制标题
细分图的图兰数
DOI：
10.1137/100819254
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
R. Seiver
中科院分区：
文献类型：
--
作者：
T. Jiang;R. Seiver
给定一个正整数$n$和一个图$F$，Turan数$ex（n，F）$是不包含$F$作为子图的$n$-顶点简单图的最大边数。设$H$是一个图，$p$是一个正偶数.设$H^{（p）}$表示由$H$通过将其每条边细分$p-1$次而得到的图。我们证明了$ex（n，H^{（p）}）=O（n^{1+（16/p）}）$.这是从一个更一般的结果，我们建立，其中不同的边缘$H$被允许细分不同的次数。我们的结果与Jiang [J. Graph Theory，67（2011），pp. 139- 152]和Kostochka和Pyber [Combinatorica，8（1988），pp. 83- 86]上的拓扑子式。
Given a positive integer $n$ and a graph $F$, the Turan number $ex(n,F)$ is the maximum number of edges in an $n$-vertex simple graph that does not contain $F$ as a subgraph. Let $H$ be a graph and $p$ a positive even integer. Let $H^{(p)}$ denote the graph obtained from $H$ by subdividing each of its edges $p-1$ times. We prove that $ex(n,H^{(p)})=O(n^{1+(16/p)})$. This follows from a more general result that we establish, where different edges of $H$ are allowed to be subdivided different numbers of times. Our result is closely related to the results of Jiang [J. Graph Theory, 67 (2011), pp. 139--152] and of Kostochka and Pyber [Combinatorica, 8 (1988), pp. 83--86] on topological minors.