论文标题
饱和数的下限，并为其尖锐的图形
A lower bound on the saturation number, and graphs for which it is sharp
论文作者
论文摘要
令$ h $为固定图。我们说，如果$ g $没有子图的同构为$ h $，则是$ h $饱和的，但是将任何优势添加到$ g $的结果中。饱和数$ \ mathrm {sat}（h，n）$是$ n $ vertices上$ h $饱和图中的最小边数。 Kászonyi和Tuza于1986年对图$ H $的饱和数进行了一般的上限，但非平凡的下限仍然难以捉摸。在本文中，我们在$ \ mathrm {sat}（h，n）$上给出了一般的下限，并证明它在一大群图上渐近（添加常数）是渐近的。此类包括所有阈值图和许多以前确切确定饱和数的图。因此，我们的工作给出了几个早期结果的渐近共同概括。该课程还包括分支机构的脱节工会，使我们能够解决Faudree，Ferrara，Gould和Jacobson的开放问题。
Let $H$ be a fixed graph. We say that a graph $G$ is $H$-saturated if it has no subgraph isomorphic to $H$, but the addition of any edge to $G$ results in an $H$-subgraph. The saturation number $\mathrm{sat}(H,n)$ is the minimum number of edges in an $H$-saturated graph on $n$ vertices. Kászonyi and Tuza, in 1986, gave a general upper bound on the saturation number of a graph $H$, but a nontrivial lower bound has remained elusive. In this paper we give a general lower bound on $\mathrm{sat}(H,n)$ and prove that it is asymptotically sharp (up to an additive constant) on a large class of graphs. This class includes all threshold graphs and many graphs for which the saturation number was previously determined exactly. Our work thus gives an asymptotic common generalization of several earlier results. The class also includes disjoint unions of cliques, allowing us to address an open problem of Faudree, Ferrara, Gould, and Jacobson.
