solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看2953次
Few $T$ copies in $H$-saturated graphs. (arXiv:1810.00939v1 [math.CO])
来源于:arXiv
A graph is $F$-saturated if it is $F$-free but the addition of any edge
creates a copy of $F$. In this paper we study the quantity $\mathrm{sat}(n, H,
F)$ which denotes the minimum number of copies of $H$ that an $F$-saturated
graph on $n$ vertices may contain. This parameter is a natural saturation
analogue of Alon and Shikhelmen's generalized Tur\'an problem, and letting $H =
K_2$ recovers the well-studied saturation function. We provide a first
investigation into this general function focusing on the cases where the host
graph is either $K_s$ or $C_k$-saturated. Some representative interesting
behavior is:
(a) For any natural number $m$, there are graphs $H$ and $F$ such that
$\mathrm{sat}(n, H, F) = \Theta(n^m)$.
(b) For many pairs $k$ and $l$, we show $\mathrm{sat}(n, C_l, C_k) = 0$. In
particular, we prove that there exists a triangle-free $C_k$-saturated graphs
on $n$ vertices for any $k > 4$ and large enough $n$.
(c) $\mathrm{sat}(n, K_3, K_4) = n-2$, $\mathrm{sat}(n, C_4, K 查看全文>>