论文标题
集团中完整的两分图的饱和数弱
Weak saturation numbers of complete bipartite graphs in the clique
论文作者
论文摘要
Bollobás于1968年提出了弱饱和度的概念。让$ f $和$ h $为图。一个跨度子图$ g \ subseteq f $是薄弱的$（f，h）$ - 如果不包含$ h $的副本，但存在订购$ e_1，\ ldots，e_t $ of $ e（f）\ setminus e（g）$，以便每张$ i \ in [t] $ i \ in [t] \ {e_1，\ ldots，e_i \} $包含$ h $的$ h'$ of $ h $，因此$ e_i \ in H'$。定义$ wsat（f，h）$是弱$（f，h）$饱和图中的最小边数。在本文中，我们证明了所有$ t \ ge 2 $和$ n \ ge 3t-3 $，$ wsat（k_n，k_ {t，t，t，t}）=（t-1）（n + 1- t/2）$，我们确定$ wsat（k_n，k_n，k_ {t-1，t}）$的值。对于固定的$ 2 \ le s <t $，我们还可以在$ wsat（k_n，k_ {s，t}）上获得渐近紧密的界限。
The notion of weak saturation was introduced by Bollobás in 1968. Let $F$ and $H$ be graphs. A spanning subgraph $G \subseteq F$ is weakly $(F,H)$-saturated if it contains no copy of $H$ but there exists an ordering $e_1,\ldots,e_t$ of $E(F)\setminus E(G)$ such that for each $i \in [t]$, the graph $G \cup \{e_1,\ldots,e_i\}$ contains a copy $H'$ of $H$ such that $e_i \in H'$. Define $wsat(F,H)$ to be the minimum number of edges in a weakly $(F,H)$-saturated graph. In this paper, we prove for all $t \ge 2$ and $n \ge 3t-3$, that $wsat(K_n,K_{t,t}) = (t-1)(n + 1 - t/2)$, and we determine the value of $wsat(K_n,K_{t-1,t})$ as well. For fixed $2 \le s < t$, we also obtain bounds on $wsat(K_n,K_{s,t})$ that are asymptotically tight.
