论文标题
最小数量的集团饱和边缘数量
The minimum number of clique-saturating edges
论文作者
论文摘要
令$ g $为$ k_p $ -free Graph。我们说，$ e $是$ k_p $ - 饱和的边缘，如果$ e \ notin e（g）$和$ g+e $包含$ k_p $的副本。用$ f_p（n，e）$表示$ k_p $ - 饱和的边缘的最低数量，即$ n $ vertex $ k_p $ -free-e $ edges可以拥有。 erdős和tuza猜想$ f_4（n，\ lfloor n^2/4 \ rfloor + 1）= \ left（1 + o（1）\ right）\ frac {n^2} {16} {16} {16} {16} {16}。 n^2/4 \ rfloor+1）=（1+O（1））\ frac {2n^2} {33} $。他们认为，$ k_p $ - 免费图的建筑自然概括也应该是最佳的，并提出了$ f_ {p+1}}（n，ex（n，ex（n，k_p）+1）= \ left（\ frac {2（p-2（p-2）^2}^2} p（4p^2-1p+8）$ pe（4p^2-11p+8）+p $ p（frac {2（p-2）+p， 3 $。本文的主要结果是确认上述Balogh和Liu的猜想。
Let $G$ be a $K_p$-free graph. We say $e$ is a $K_p$-saturating edge of $G$ if $e\notin E(G)$ and $G+e$ contains a copy of $K_p$. Denote by $f_p(n, e)$ the minimum number of $K_p$-saturating edges that an $n$-vertex $K_p$-free graph with $e$ edges can have. Erdős and Tuza conjectured that $f_4(n,\lfloor n^2/4\rfloor+1)=\left(1 + o(1)\right)\frac{n^2}{16}.$ Balogh and Liu disproved this by showing $f_4(n,\lfloor n^2/4\rfloor+1)=(1+o(1))\frac{2n^2}{33}$. They believed that a natural generalization of their construction for $K_p$-free graph should also be optimal and made a conjecture that $f_{p+1}(n,ex(n,K_p)+1)=\left(\frac{2(p-2)^2}{p(4p^2-11p+8)}+o(1)\right)n^2$ for all integers $p\ge 3$. The main result of this paper is to confirm the above conjecture of Balogh and Liu.
