论文标题
关于erds的问题，关于图形的大小为Turán数字加一个
On a problem of Erdős about graphs whose size is the Turán number plus one
论文作者
论文摘要
我们考虑有限的简单图。给定图形$ h $和一个正整数$ n，$ n $ h $的$ h $，$ n，$表示$ {\ rm ex}（n，h），$是订单$ n $的最大大小，不包含$ h $作为子Graph。 ERDS在1990年提出了以下问题： “对于哪个图，$ h $的确是$ n $顶点上的每个图和$ {\ rm ex}（n，h）+1 $边缘至少包含两个$ h $ s？也许这始终是正确的。” 我们通过证明每个整数$ k \ ge 4，存在一个图$ h $ of $ k $和至少两个订单$ n $，从而解决了一个否定的$ n $ $ n $和size $ n $和size $ {\ rm ex ex}（n，h）+1 $，其中包含$ h. $ c_ $ c_4 $ c_4 $，我们将解决此问题的第二部分。我们还证明，对于每一个整数$ n $，$ 6 \ le n \ le 11，存在$ n $的订单图和尺寸$ n $和$ {\ rm ex}（n，c_4）+1 $，它包含$ c_4的一个副本，$ c_4，$，但$ n = 12 $ n = 12 $ n = 13 $ n = 13，$ n = 13，$ c_4 $ n $ c_4 $ nmime $ n $ nmime $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n。 ex}（n，c_4）+1 $是$2。$
We consider finite simple graphs. Given a graph $H$ and a positive integer $n,$ the Turán number of $H$ for the order $n,$ denoted ${\rm ex}(n,H),$ is the maximum size of a graph of order $n$ not containing $H$ as a subgraph. Erdős posed the following problem in 1990: "For which graphs $H$ is it true that every graph on $n$ vertices and ${\rm ex}(n,H)+1$ edges contains at least two $H$s? Perhaps this is always true." We solve the second part of this problem in the negative by proving that for every integer $k\ge 4,$ there exists a graph $H$ of order $k$ and at least two orders $n$ such that there exists a graph of order $n$ and size ${\rm ex}(n,H)+1$ which contains exactly one copy of $H.$ Denote by $C_4$ the $4$-cycle. We also prove that for every integer $n$ with $6\le n\le 11,$ there exists a graph of order $n$ and size ${\rm ex}(n,C_4)+1$ which contains exactly one copy of $C_4,$ but for $n=12$ or $n=13,$ the minimum number of copies of $C_4$ in a graph of order $n$ and size ${\rm ex}(n,C_4)+1$ is $2.$
